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

#include <KdTree.h>

Collaboration diagram for CCCoreLib::KDTree:

[legend]

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

Public Member Functions
	KDTree ()
	Default constructor.

virtual	~KDTree ()
	Destructor.

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	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)
	Searches for the points that lie to a given distance (up to a tolerance) from a query point. More...

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.

void	updateInsideBoundingBox (KdCell *cell)
	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.

void	updateOutsideBoundingBox (KdCell *cell)
	Computes a cell outside bounding box using the father one and the cutting plane.

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)
	Computes the distance between a point and the outside bounding box of the cell in which it lies. More...

void	pointToCellDistances (const PointCoordinateType queryPoint, KdCell cell, ScalarType &min, ScalarType &max)
	Computes the distances (min & max) between a point and a cell inside bounding box. More...

int	checkNearerPointInSubTree (const PointCoordinateType queryPoint, ScalarType &maxSqrDist, KdCell cell)
	Checks if there is a point in KdCell that is less than minDist-apart from the query point, starting from cell cell. More...

bool	checkDistantPointInSubTree (const PointCoordinateType queryPoint, ScalarType &maxSqrDist, KdCell cell)
	Checks if there is a point in KdCell that is less than minDist-apart from the query point, starting from cell cell. More...

void	distanceScanTree (const PointCoordinateType queryPoint, ScalarType distance, ScalarType tolerance, KdCell cell, std::vector< unsigned > &localArray)
	Recursive function which store every point lying to a given distance from the query point. More...

Protected Attributes
KdCell *	m_root
	Tree root.

std::vector< unsigned >	m_indexes
	Point indexes.

GenericIndexedCloud *	m_associatedCloud
	Associated cloud.

unsigned	m_cellCount
	Number of cells.

Detailed Description

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

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

◆ 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)

◆ 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

◆ 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

◆ 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

◆ 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

◆ 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())

◆ 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

◆ getAssociatedCloud()

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

inline

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

Returns: associated cloud

◆ 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.

◆ 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

◆ 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

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

KdTree.h
KdTree.cpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ buildFromCloud()

◆ buildSubTree()

◆ checkDistantPointInSubTree()

◆ checkNearerPointInSubTree()

◆ distanceScanTree()

◆ findNearestNeighbour()

◆ findPointBelowDistance()

◆ findPointsLyingToDistance()

◆ getAssociatedCloud()

◆ InsidePointToCellDistance()

◆ pointToCellDistances()

◆ pointToCellSquareDistance()