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;
}

Further Reading