KDTree Class Reference

#include <kdtree.h>

Detailed Description

class to find closest points in space for a given point cloud

Public Member Functions

 KDTree ()
 
Result< void > Init (Int maxThreads)
 
void Free ()
 
Result< void > Insert (const Vector &point, Int idValue)
 
void Balance ()
 
Int FindNearest (Int threadIndex, const Vector &point, KDTreeNearest *nearest)
 
Int FindNearest (Int threadIndex, const Vector &point, Float maxDistance, BaseArray< KDTreeNearest > &list, Int maxElements, Bool sortResults)
 
Int FindRange (Int threadIndex, const Vector &point, Float maxDistance, BaseArray< KDTreeNearest > &list, Bool sortResults)
 

Private Member Functions

 MAXON_DISALLOW_COPY_AND_ASSIGN (KDTree)
 
KDTreeNodeBalance (Int index, Int count)
 
void InsertElement (BaseArray< KDTreeNearest > &list, Int &count, Float &maxRangeSquare, Int maxElements, KDTreeNode *node, Float distanceSquare)
 
Bool AppendElement (BaseArray< KDTreeNearest > &list, KDTreeNode *node, Float distance)
 

Private Attributes

KDTreeNode_root
 
BaseArray< KDTreeNode_nodelist
 
PointerArray< KDStackArray_stack
 

Constructor & Destructor Documentation

◆ KDTree()

KDTree ( )

Member Function Documentation

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN ( KDTree  )
private

◆ Init()

Result<void> Init ( Int  maxThreads)

Initialize the kd-tree.

Parameters
[in]maxThreadsMaximum number of threads using the tree at the same time. set to 1 if no MP is used.
Returns
OK on success.

◆ Free()

void Free ( )

free the kd-tree and helper arrays

◆ Insert()

Result<void> Insert ( const Vector point,
Int  idValue 
)

Insert a node into the kd-tree.

Returns
OK on success.

◆ Balance() [1/2]

void Balance ( )

balance the kd-tree. This needs to be done once after all nodes have been inserted calling 'Insert'

◆ FindNearest() [1/2]

Int FindNearest ( Int  threadIndex,
const Vector point,
KDTreeNearest nearest 
)

Find the nearest node in the kd-tree.

Parameters
[in]threadIndexIndex of thread using the tree, set to 0 if no MP is used.
[in]pointPoint in space that is searched for.
[out]nearestOptional, can be nullptr. If provided the structure will be filled with information about the nearest node.
Returns
Returns the index of the nearest node or NOTOK if there is no nearest node.

◆ FindNearest() [2/2]

Int FindNearest ( Int  threadIndex,
const Vector point,
Float  maxDistance,
BaseArray< KDTreeNearest > &  list,
Int  maxElements,
Bool  sortResults 
)

Find the nearest nodes in the kd-tree note: for performance reasons this routine should only be called if the maximum number of searched nodes is sufficiently small (<100), otherwise FindRange is the better choice.

Parameters
[in]threadIndexIndex of thread using the tree, set to 0 if no MP is used.
[in]pointPoint in space that is searched for.
[in]maxDistanceOptional, can be MAXVALUE_FLOAT. If provided only nodes within this distance are searched.
[out]listArray that will be filled with search results. the array doesn't have to be initialized before, this will be done inside the routine. for performance reasons try to re-use the array, so that memory doesn't have to be allocated each time.
[in]maxElementsMaximum number of elements that shall be searched for.
[in]sortResultsIf true the resulting array will be sorted by distance, starting with the closest point.
Returns
Returns the number of found nodes or 0 if there was not enough memory.

◆ FindRange()

Int FindRange ( Int  threadIndex,
const Vector point,
Float  maxDistance,
BaseArray< KDTreeNearest > &  list,
Bool  sortResults 
)

Find all nodes within a radius in the kd-tree note depending on the structure of the tree there can be a lot of search results (in an extreme case as many as there are nodes in the tree, which costs SIZEOF(KDTreeNearest)*nodes bytes memory.

Parameters
[in]threadIndexIndex of thread using the tree, set to 0 if no MP is used.
[in]pointPoint in space that is searched for.
[in]maxDistanceDistance that nodes are searched within.
[out]listArray that will be filled with search results. the array doesn't have to be initialized before, this will be done inside the routine. for performance reasons try to re-use the array, so that memory doesn't have to be allocated each time.
[in]sortResultsIf true the resulting array will be sorted by distance, starting with the closest point.
Returns
Returns the number of found nodes or 0 if there was not enough memory.

◆ Balance() [2/2]

KDTreeNode* Balance ( Int  index,
Int  count 
)
private

◆ InsertElement()

void InsertElement ( BaseArray< KDTreeNearest > &  list,
Int count,
Float maxRangeSquare,
Int  maxElements,
KDTreeNode node,
Float  distanceSquare 
)
private

◆ AppendElement()

Bool AppendElement ( BaseArray< KDTreeNearest > &  list,
KDTreeNode node,
Float  distance 
)
private

Member Data Documentation

◆ _root

KDTreeNode* _root
private

◆ _nodelist

BaseArray<KDTreeNode> _nodelist
private

◆ _stack

PointerArray<KDStackArray> _stack
private