KDTree Manual

Table of Contents

• About
• KDTree
• Further Reading

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:

• maxon::KDTree::KDTree(): Class constructor.
• maxon::KDTree::Init(): Initializes the tree to be used by one or many threads.
• maxon::KDTree::Free(): Frees the tree's internal data.

The tree is filled with:

• maxon::KDTree::Insert(): Inserts the given point into the tree.
• maxon::KDTree::Balance(): Balances the tree. Must be called after all points were inserted.

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

• maxon::KDTree::FindNearest(): Returns the index of the nearest point or points.
• maxon::KDTree::FindRange(): Finds all nodes within the given radius.

  // 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
  maxon::KDTree tree;
  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
 
  maxon::BaseArray<maxon::Int> nearestPoints;
  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

• Algorithms
• Vectors