KDTree Manual

Table of Contents

About

A k-d tree organizes a given set of points in three-dimensional space. It is used to search quickly for the point nearest to a given point.

KDTree

A maxon::KDTree is simply created with:

The tree is filled with:

The nearest point for a given point in space can be found with:

// This example creates and fills a k-d tree. The tree is then
// used to search the nearest points for the given sample points.
// create k-d tree for single-threaded use
tree.Init(1) iferr_return;
// insert points
for (maxon::Int i = 0; i < pointCnt; ++i)
{
tree.Insert(points[i], i) iferr_return;
}
// balance tree
tree.Balance();
// search for nearest points next to the sample points
nearestPoints.EnsureCapacity(samplePointCnt) iferr_return;
for (const maxon::Vector& samplePoint : samplePoints)
{
// find nearest point
const maxon::Int nearestIndex = tree.FindNearest(0, samplePoint, nullptr);
nearestPoints.Append(nearestIndex) iferr_return;
}
Py_ssize_t i
Definition: abstract.h:645
Definition: basearray.h:415
ResultMem EnsureCapacity(Int requestedCapacity, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
Definition: basearray.h:1320
MAXON_ATTRIBUTE_FORCE_INLINE ResultRef< T > Append(ARG &&x)
Appends a new element at the end of the array and constructs it using the forwarded value.
Definition: basearray.h:619
class to find closest points in space for a given point cloud
Definition: kdtree.h:99
Result< void > Init(Int maxThreads)
void Balance()
balance the kd-tree. This needs to be done once after all nodes have been inserted calling 'Insert'
Int FindNearest(Int threadIndex, const Vector &point, KDTreeNearest *nearest)
Result< void > Insert(const Vector &point, Int idValue)
Int64 Int
signed 32/64 bit int, size depends on the platform
Definition: apibase.h:213
#define iferr_return
Definition: resultbase.h:1521

Further Reading