#include <CVKdTree.h>

Collaboration diagram for cloudViewer::KDTree:

[legend]

Classes
struct	KdCell
	A KDTre cell struct. More...

Public Member Functions
	KDTree ()
	Default constructor. More...

virtual	~KDTree ()
	Destructor. More...

bool	buildFromCloud (GenericIndexedCloud cloud, GenericProgressCallback progressCb=nullptr)
	Builds the KD-tree. More...

GenericIndexedCloud *	getAssociatedCloud () const
	Gets the point cloud from which the tree has been build. More...

bool	findNearestNeighbour (const PointCoordinateType *queryPoint, unsigned &nearestPointIndex, ScalarType maxDist)
	Nearest point search. More...

bool	findNearestNeighbourWithMaxDist (const PointCoordinateType *queryPoint, ScalarType maxDist)
	Optimized version of findNearestNeighbour with a maximum distance. More...

unsigned	radiusSearch (const PointCoordinateType *queryPoint, ScalarType distance, ScalarType tolerance, std::vector< unsigned > &pointndexes)

bool	findPointBelowDistance (const PointCoordinateType *queryPoint, ScalarType maxDist)
	Optimized version of nearest point search method. More...

unsigned	findPointsLyingToDistance (const PointCoordinateType *queryPoint, ScalarType distance, ScalarType tolerance, std::vector< unsigned > &points)

Protected Member Functions
KdCell *	buildSubTree (unsigned first, unsigned last, KdCell father, unsigned &nbBuildCell, GenericProgressCallback progressCb=nullptr)
	Builds a sub tree. More...

void	deleteSubTree (KdCell *cell)
	Deletes a sub tree. More...

void	updateInsideBoundingBox (KdCell *cell)

void	updateOutsideBoundingBox (KdCell *cell)

ScalarType	pointToCellSquareDistance (const PointCoordinateType queryPoint, KdCell cell)
	Computes the distance between a point and a cell inside bounding box. More...

ScalarType	insidePointToCellDistance (const PointCoordinateType queryPoint, KdCell cell)

void	pointToCellDistances (const PointCoordinateType queryPoint, KdCell cell, ScalarType &min, ScalarType &max)

int	checkNearerPointInSubTree (const PointCoordinateType queryPoint, ScalarType &maxSqrDist, KdCell cell)

bool	checkDistantPointInSubTree (const PointCoordinateType queryPoint, ScalarType &maxSqrDist, KdCell cell)

void	distanceScanTree (const PointCoordinateType queryPoint, ScalarType distance, ScalarType tolerance, KdCell cell, std::vector< unsigned > &localArray)

Protected Attributes
KdCell *	m_root
	Tree root. More...

std::vector< unsigned >	m_indexes
	Point indexes. More...

GenericIndexedCloud *	m_associatedCloud
	Associated cloud. More...

unsigned	m_cellCount
	Number of cells. More...

Detailed Description

A Kd Tree Class which implements functions related to point to point distance

Definition at line 20 of file CVKdTree.h.

Constructor & Destructor Documentation

◆ KDTree()

KDTree::KDTree ( )

Default constructor.

Definition at line 18 of file CVKdTree.cpp.

◆ ~KDTree()

KDTree::~KDTree ( )

virtual

Destructor.

Definition at line 21 of file CVKdTree.cpp.

References deleteSubTree(), and m_root.

Member Function Documentation

◆ buildFromCloud()

bool KDTree::buildFromCloud	(	GenericIndexedCloud *	cloud,
		GenericProgressCallback *	progressCb = `nullptr`
	)

Builds the KD-tree.

Parameters

cloud	the point cloud from which to buil the KDtree
progressCb	the client method can get some notification of the process progress through this callback mechanism (see GenericProgressCallback)

Returns: success

Definition at line 23 of file CVKdTree.cpp.

References buildSubTree(), m_associatedCloud, m_cellCount, m_indexes, m_root, cloudViewer::GenericProgressCallback::setInfo(), cloudViewer::GenericCloud::size(), cloudViewer::GenericProgressCallback::start(), cloudViewer::GenericProgressCallback::stop(), cloudViewer::GenericProgressCallback::textCanBeEdited(), and cloudViewer::GenericProgressCallback::update().

Referenced by define_KdTree(), cloudViewer::FPCSRegistrationTools::FindCongruentBases(), and cloudViewer::FPCSRegistrationTools::RegisterClouds().

◆ buildSubTree()

KDTree::KdCell * KDTree::buildSubTree	(	unsigned	first,
		unsigned	last,
		KdCell *	father,
		unsigned &	nbBuildCell,
		GenericProgressCallback *	progressCb = `nullptr`
	)

protected

Builds a sub tree.

Parameters

first	first index
last	last index
father	father cell
nbBuildCell	nbBuildCell
progressCb	the client method can get some notification of the process progress through this callback mechanism (see GenericProgressCallback)

Returns: sub tree (cell)

Definition at line 108 of file CVKdTree.cpp.

References ComparisonX(), ComparisonY(), ComparisonZ(), cloudViewer::KDTree::KdCell::cuttingCoordinate, cloudViewer::KDTree::KdCell::cuttingDim, deleteSubTree(), cloudViewer::KDTree::KdCell::father, cloudViewer::GenericIndexedCloud::getPoint(), cloudViewer::KDTree::KdCell::gSon, cloudViewer::KDTree::KdCell::leSon, m_associatedCloud, m_cellCount, m_indexes, cloudViewer::KDTree::KdCell::nbPoints, s_comparisonCloud, cloudViewer::KDTree::KdCell::startingPointIndex, Tuple3Tpl< Type >::u, cloudViewer::GenericProgressCallback::update(), updateInsideBoundingBox(), and updateOutsideBoundingBox().

Referenced by buildFromCloud().

◆ checkDistantPointInSubTree()

bool KDTree::checkDistantPointInSubTree	(	const PointCoordinateType *	queryPoint,
		ScalarType &	maxSqrDist,
		KdCell *	cell
	)

protected

Checks if there is a point in KdCell that is less than minDist-apart from the query point, starting from cell cell Optimiszed version of CheckNearerPointInSubTree since we don't want to find the nearest point, but only check if there is a point that is close enough

Parameters

queryPoint	the query Point coordinates
maxSqrDist	square of the maximal distance from querypoint
cell	kdtree-cell from which to start the research

Returns: true if there is a point in the subtree starting at cell that is close enough from the query point

Definition at line 528 of file CVKdTree.cpp.

References dist(), cloudViewer::GenericIndexedCloud::getPoint(), cloudViewer::KDTree::KdCell::gSon, cloudViewer::KDTree::KdCell::leSon, m_associatedCloud, m_indexes, cloudViewer::KDTree::KdCell::nbPoints, pointToCellSquareDistance(), cloudViewer::KDTree::KdCell::startingPointIndex, Tuple3Tpl< Type >::u, and Vector3Tpl< PointCoordinateType >::vdistance2().

Referenced by findNearestNeighbourWithMaxDist(), and findPointBelowDistance().

◆ checkNearerPointInSubTree()

int KDTree::checkNearerPointInSubTree	(	const PointCoordinateType *	queryPoint,
		ScalarType &	maxSqrDist,
		KdCell *	cell
	)

protected

Checks if there is a point in KdCell that is less than minDist-apart from the query point, starting from cell cell

Parameters

queryPoint	the query Point coordinates
maxSqrDist	square of the maximal distance from querypoint
cell	kdtree-cell from which to start the research

Returns: -1 if there is no nearer point from querypoint. The nearest point index found in cell if there is one that is at most maxdist apart from querypoint

Definition at line 502 of file CVKdTree.cpp.

References dist(), cloudViewer::GenericIndexedCloud::getPoint(), cloudViewer::KDTree::KdCell::gSon, cloudViewer::KDTree::KdCell::leSon, m_associatedCloud, m_indexes, cloudViewer::KDTree::KdCell::nbPoints, pointToCellSquareDistance(), cloudViewer::KDTree::KdCell::startingPointIndex, Tuple3Tpl< Type >::u, and Vector3Tpl< PointCoordinateType >::vdistance2().

Referenced by findNearestNeighbour().

◆ deleteSubTree()

void KDTree::deleteSubTree ( KdCell * cell )

protected

Deletes a sub tree.

Definition at line 76 of file CVKdTree.cpp.

References cloudViewer::KDTree::KdCell::gSon, cloudViewer::KDTree::KdCell::leSon, and m_cellCount.

Referenced by buildSubTree(), and ~KDTree().

◆ distanceScanTree()

void KDTree::distanceScanTree	(	const PointCoordinateType *	queryPoint,
		ScalarType	distance,
		ScalarType	tolerance,
		KdCell *	cell,
		std::vector< unsigned > &	localArray
	)

protected

Recursive function which store every point lying to a given distance from the query point

Parameters

	queryPoint	the query point coordinates
	distance	the wished distance from the query point
	tolerance	tolerance for resulting points : p is in resulting array if \|\|p-queryPoint\|\|<=tolerance
	cell	current cell to explore (used for recursion)
[out]	localArray	output of the algorithm. Resulting points m_indexes in associatedCloud are stored in this array

Definition at line 551 of file CVKdTree.cpp.

References dist(), cloudViewer::GenericIndexedCloud::getPoint(), cloudViewer::KDTree::KdCell::gSon, cloudViewer::KDTree::KdCell::leSon, m_associatedCloud, m_indexes, max(), min(), cloudViewer::KDTree::KdCell::nbPoints, pointToCellDistances(), cloudViewer::KDTree::KdCell::startingPointIndex, Tuple3Tpl< Type >::u, and Vector3Tpl< PointCoordinateType >::vdistance().

Referenced by findPointsLyingToDistance(), and radiusSearch().

◆ findNearestNeighbour()

bool KDTree::findNearestNeighbour	(	const PointCoordinateType *	queryPoint,
		unsigned &	nearestPointIndex,
		ScalarType	maxDist
	)

Nearest point search.

Parameters

queryPoint	coordinates of the query point from which we want the nearest point in the tree
nearestPointIndex	[out] index of the point that lies the nearest from query Point. Corresponding coordinates can be retrieved using getAssociatedCloud()->getPoint(nearestPointIndex)
maxDist	distance above which the function doesn't consider points

Returns: true if it finds a point p such that ||p-queryPoint||<=maxDist. False otherwise

Definition at line 178 of file CVKdTree.cpp.

References checkNearerPointInSubTree(), cloudViewer::KDTree::KdCell::cuttingCoordinate, cloudViewer::KDTree::KdCell::cuttingDim, cloudViewer::KDTree::KdCell::father, cloudViewer::GenericIndexedCloud::getPoint(), cloudViewer::KDTree::KdCell::gSon, insidePointToCellDistance(), cloudViewer::KDTree::KdCell::leSon, m_associatedCloud, m_indexes, m_root, cloudViewer::KDTree::KdCell::nbPoints, cloudViewer::KDTree::KdCell::startingPointIndex, Tuple3Tpl< Type >::u, and Vector3Tpl< PointCoordinateType >::vdistance2().

Referenced by cloudViewer::FPCSRegistrationTools::FindCongruentBases().

◆ findNearestNeighbourWithMaxDist()

bool KDTree::findNearestNeighbourWithMaxDist	(	const PointCoordinateType *	queryPoint,
		ScalarType	maxDist
	)

Optimized version of findNearestNeighbour with a maximum distance.

Only checks if there is a point p into the tree such that ||p-queryPoint||<=maxDist (see FindNearestNeighbour())

Definition at line 235 of file CVKdTree.cpp.

References checkDistantPointInSubTree(), cloudViewer::KDTree::KdCell::cuttingCoordinate, cloudViewer::KDTree::KdCell::cuttingDim, cloudViewer::KDTree::KdCell::father, cloudViewer::GenericIndexedCloud::getPoint(), cloudViewer::KDTree::KdCell::gSon, insidePointToCellDistance(), cloudViewer::KDTree::KdCell::leSon, m_associatedCloud, m_indexes, m_root, cloudViewer::KDTree::KdCell::nbPoints, cloudViewer::KDTree::KdCell::startingPointIndex, Tuple3Tpl< Type >::u, and Vector3Tpl< PointCoordinateType >::vdistance2().

◆ findPointBelowDistance()

bool KDTree::findPointBelowDistance	(	const PointCoordinateType *	queryPoint,
		ScalarType	maxDist
	)

Optimized version of nearest point search method.

Only checks if there is a point p into the tree such that ||p-queryPoint||<=maxDist (see FindNearestNeighbour())

Definition at line 301 of file CVKdTree.cpp.

References checkDistantPointInSubTree(), cloudViewer::KDTree::KdCell::cuttingCoordinate, cloudViewer::KDTree::KdCell::cuttingDim, cloudViewer::KDTree::KdCell::father, cloudViewer::GenericIndexedCloud::getPoint(), cloudViewer::KDTree::KdCell::gSon, insidePointToCellDistance(), cloudViewer::KDTree::KdCell::leSon, m_associatedCloud, m_indexes, m_root, cloudViewer::KDTree::KdCell::nbPoints, cloudViewer::KDTree::KdCell::startingPointIndex, Tuple3Tpl< Type >::u, and Vector3Tpl< PointCoordinateType >::vdistance2().

Referenced by cloudViewer::FPCSRegistrationTools::ComputeRegistrationScore().

◆ findPointsLyingToDistance()

unsigned KDTree::findPointsLyingToDistance	(	const PointCoordinateType *	queryPoint,
		ScalarType	distance,
		ScalarType	tolerance,
		std::vector< unsigned > &	points
	)

Searches for the points that lie to a given distance (up to a tolerance) from a query point

Parameters

queryPoint	query point coordinates
distance	distance wished between the query point and resulting points
tolerance	error allowed by the function : each resulting point p is such that distance-tolerance<=\|\|p-queryPoint\|\|<=distance+tolerance
points	[out] array of point m_indexes. Each point stored in this array lie to distance (up to tolerance) from queryPoint

Returns: the number of matching points

Definition at line 347 of file CVKdTree.cpp.

References distanceScanTree(), m_root, and points.

Referenced by cloudViewer::FPCSRegistrationTools::FindCongruentBases().

◆ getAssociatedCloud()

GenericIndexedCloud* cloudViewer::KDTree::getAssociatedCloud ( ) const

inline

Gets the point cloud from which the tree has been build.

Returns: associated cloud

Definition at line 40 of file CVKdTree.h.

Referenced by define_KdTree(), and cloudViewer::FPCSRegistrationTools::FindCongruentBases().

◆ insidePointToCellDistance()

ScalarType KDTree::insidePointToCellDistance	(	const PointCoordinateType *	queryPoint,
		KdCell *	cell
	)

protected

Computes the distance between a point and the outside bounding box of the cell in which it lies.

Parameters

queryPoint	the query point coordinates
cell	the cell containting the query point

Returns: the distance between the point and the cell border. If this value is negative, it means that the cell has no border.

Definition at line 462 of file CVKdTree.cpp.

References abs(), cloudViewer::KDTree::KdCell::boundsMask, max(), min(), cloudViewer::KDTree::KdCell::outbbmax, cloudViewer::KDTree::KdCell::outbbmin, Tuple3Tpl< Type >::x, Tuple3Tpl< Type >::y, and Tuple3Tpl< Type >::z.

Referenced by findNearestNeighbour(), findNearestNeighbourWithMaxDist(), and findPointBelowDistance().

◆ pointToCellDistances()

void KDTree::pointToCellDistances	(	const PointCoordinateType *	queryPoint,
		KdCell *	cell,
		ScalarType &	min,
		ScalarType &	max
	)

protected

Computes the distances (min & max) between a point and a cell inside bounding box

Parameters

queryPoint	the query point coordinates
cell	the cell from which we want to compute the distance
min	[out] the minimal distance between the query point and the inside bounding box of cell
max	[out] the maximal distance between the query point and the inside bounding box of cell

Definition at line 446 of file CVKdTree.cpp.

References abs(), cloudViewer::KDTree::KdCell::inbbmax, cloudViewer::KDTree::KdCell::inbbmin, max(), min(), pointToCellSquareDistance(), Tuple3Tpl< Type >::x, Tuple3Tpl< Type >::y, and Tuple3Tpl< Type >::z.

Referenced by distanceScanTree().

◆ pointToCellSquareDistance()

ScalarType KDTree::pointToCellSquareDistance	(	const PointCoordinateType *	queryPoint,
		KdCell *	cell
	)

protected

Computes the distance between a point and a cell inside bounding box.

Parameters

queryPoint	queryPoint coordinates
cell	the cell from which we want to compute the distance

Returns: 0 if the point is inside the cell, the suare of the distance between the two elements if the point is outside

Definition at line 419 of file CVKdTree.cpp.

References abs(), cloudViewer::KDTree::KdCell::inbbmax, cloudViewer::KDTree::KdCell::inbbmin, min(), Tuple3Tpl< Type >::x, Tuple3Tpl< Type >::y, and Tuple3Tpl< Type >::z.

Referenced by checkDistantPointInSubTree(), checkNearerPointInSubTree(), and pointToCellDistances().

◆ radiusSearch()

unsigned KDTree::radiusSearch	(	const PointCoordinateType *	queryPoint,
		ScalarType	distance,
		ScalarType	tolerance,
		std::vector< unsigned > &	pointndexes
	)

Searches for the points that lie at a given distance (+/-tolerance) from a query point

Parameters

	queryPoint	query point coordinates
	distance	distance wished between the query point and resulting points
	tolerance	distance tolerance: p is selected if distance-tolerance<=\|\|p-queryPoint\|\|<=distance+tolerance
[out]	pointndexes	array of point indexes

Returns: the number of matching points

Definition at line 288 of file CVKdTree.cpp.

References distanceScanTree(), and m_root.

◆ updateInsideBoundingBox()

void KDTree::updateInsideBoundingBox ( KdCell * cell )

protected

Computes a cell inside bounding box using the sons ones. The sons bounding boxes have to be up to date considering the points they contain.

Definition at line 359 of file CVKdTree.cpp.

References cloudViewer::GenericIndexedCloud::getPoint(), cloudViewer::KDTree::KdCell::gSon, cloudViewer::KDTree::KdCell::inbbmax, cloudViewer::KDTree::KdCell::inbbmin, cloudViewer::KDTree::KdCell::leSon, m_associatedCloud, m_indexes, max(), min(), cloudViewer::KDTree::KdCell::nbPoints, cloudViewer::KDTree::KdCell::startingPointIndex, Tuple3Tpl< Type >::x, Tuple3Tpl< Type >::y, and Tuple3Tpl< Type >::z.

Referenced by buildSubTree().

◆ updateOutsideBoundingBox()

void KDTree::updateOutsideBoundingBox ( KdCell * cell )

protected

Computes a cell outside bounding box using the father one and the cutting plane.

Definition at line 390 of file CVKdTree.cpp.

References cloudViewer::KDTree::KdCell::boundsMask, cloudViewer::KDTree::KdCell::cuttingCoordinate, cloudViewer::KDTree::KdCell::cuttingDim, cloudViewer::KDTree::KdCell::father, cloudViewer::GenericIndexedCloud::getPoint(), m_associatedCloud, m_indexes, cloudViewer::KDTree::KdCell::outbbmax, cloudViewer::KDTree::KdCell::outbbmin, cloudViewer::KDTree::KdCell::startingPointIndex, and Tuple3Tpl< Type >::u.

Referenced by buildSubTree().

Member Data Documentation

◆ m_associatedCloud

GenericIndexedCloud* cloudViewer::KDTree::m_associatedCloud

protected

Associated cloud.

Definition at line 173 of file CVKdTree.h.

Referenced by buildFromCloud(), buildSubTree(), checkDistantPointInSubTree(), checkNearerPointInSubTree(), distanceScanTree(), findNearestNeighbour(), findNearestNeighbourWithMaxDist(), findPointBelowDistance(), updateInsideBoundingBox(), and updateOutsideBoundingBox().

◆ m_cellCount

unsigned cloudViewer::KDTree::m_cellCount

protected

Number of cells.

Definition at line 175 of file CVKdTree.h.

Referenced by buildFromCloud(), buildSubTree(), and deleteSubTree().

◆ m_indexes

std::vector<unsigned> cloudViewer::KDTree::m_indexes

protected

Point indexes.

Definition at line 171 of file CVKdTree.h.

Referenced by buildFromCloud(), buildSubTree(), checkDistantPointInSubTree(), checkNearerPointInSubTree(), distanceScanTree(), findNearestNeighbour(), findNearestNeighbourWithMaxDist(), findPointBelowDistance(), updateInsideBoundingBox(), and updateOutsideBoundingBox().

◆ m_root

KdCell* cloudViewer::KDTree::m_root

protected

Tree root.

Definition at line 169 of file CVKdTree.h.

Referenced by buildFromCloud(), findNearestNeighbour(), findNearestNeighbourWithMaxDist(), findPointBelowDistance(), findPointsLyingToDistance(), radiusSearch(), and ~KDTree().

The documentation for this class was generated from the following files:

/root/ACloudViewer/core/include/CVKdTree.h
/root/ACloudViewer/core/src/CVKdTree.cpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ KDTree()

◆ ~KDTree()

Member Function Documentation

◆ buildFromCloud()

◆ buildSubTree()

◆ checkDistantPointInSubTree()

◆ checkNearerPointInSubTree()

◆ deleteSubTree()

◆ distanceScanTree()

◆ findNearestNeighbour()

◆ findNearestNeighbourWithMaxDist()

◆ findPointBelowDistance()

◆ findPointsLyingToDistance()

◆ getAssociatedCloud()

◆ insidePointToCellDistance()

◆ pointToCellDistances()

◆ pointToCellSquareDistance()

◆ radiusSearch()

◆ updateInsideBoundingBox()

◆ updateOutsideBoundingBox()

Member Data Documentation

◆ m_associatedCloud

◆ m_cellCount

◆ m_indexes

◆ m_root