KD::Tree

Quickstart

This is a minimal example, missing the necessary #includes and the boilerplate Point class. The full working example can be found at test/example.cpp.

int main()
{
  typedef KD::Core<3, Point> CORE;

  Point min(0, 0, 0);
  Point max(9, 9, 9);
  KD::Tree<CORE> kdtree(min, max);

  kdtree.insert(Point(1, 2, 3));
  kdtree.insert(Point(8, 2, 5));
  kdtree.insert(Point(1, 0, 8));
  kdtree.insert(Point(3, 1, 4));

  std::cout << kdtree.nearest(Point(5, 5, 5)) << std::endl;
  return 0;
}

Methods

The KD-Tree exposes the following methods:

void insert(const Item& item)
Adds an item to the tree.
std::vector<Item> find(const Point& point, int count, Coord radius)
Returns the count closest items that lie within radius units of point.
Item nearest(const Point& point)
Returns the item closest to point. If no items are found, this method throws a std::underflow_error.
std::vector<Item> nearest(const Point& point, int count)
Returns the nearest count items to point.
std::vector<Item> within(const Point& point, Coord radius)
Returns all items within radius units of point.
void remove(const Item& item)
Removes an item from the tree.

Some notes on the above:

If count is given as an argument, the result vector may contain fewer items if there are not enough that match the search criteria.
When results are returned as a std::vector<Item>, that vector is sorted by increasing distance from the search point.
Items are passed around by value, not by reference. As such, the KD-Tree is best suited for storing pointers, acting as an index onto existing data.

Configuration

The KD-Tree takes a single template parameter, refered to as CORE throughout the internal implementation. This should be a struct with the appropriate members to fine-tune the tree's behaviour. An annotated example:

struct CORE
{
  typedef Thing* Item;  // The type we store in the tree.
  typedef Point  Point; // The type we read coordinates from.
  typedef float  Coord; // The type of individual coordinates.

  static const int DIMENSIONS =  3; // We're in a three-dimensional space.
  static const int MAX_DEPTH  = 10; // The tree will reach at most ten levels.
  static const int STORAGE    =  8; // Leaves can hold eight items before splitting.

  // Get the distance of a point along the given axis.
  static Coord coordinate(const Point& point, int axis)
  {
    return point[axis];
  }

  // Get the location of an item
  static const Point& point(const Item& item)
  {
    return item->point();
  }
};

Configuration Helpers

Most uses don't need so much control. For these cases, we provide a KD::Core template class equivalent to:

template <
  int   DIMENSIONS,
  class Item,
  class Point      = Item,
  class Coord      = double,
  int   STORAGE    = 8,
  int   MAX_DEPTH  = 32
> struct KD::Core {...};

It can be used as long as the following functions are available:

Coord Point::operator[] (int axis) const
To extract a coordinate from a point.
const Point& Item::point() const
To extract the position of an item. This function is only required if Item is neither the same type as Point nor a pointer to Point.

Implementation Details

Internally, a KD-Tree node can be one of three subtypes of the polymorphic KD::Node:

KD::Tree
A node that stores no data. It simply dispatches method calls to the nodes beneath it.
KD::Twig
A leaf node that is above CORE::MAX_DEPTH. A twig node can store up to CORE::STORAGE items, but further insertions will cause it to split, becoming a tree node with new storage nodes beneath it.
KD::Leaf
A permanent leaf node - one at CORE::MAX_DEPTH. A leaf node can hold any number of items. It begins with a capacity of CORE::STORAGE, and increases its capacity by CORE::STORAGE whenever it would overflow.

Note that unlike the canonical KD-Tree, this version stores items only in leaf (and twig) nodes. This costs a little extra storage space, but allows for some nice simplifications:

At each split, the space is divided exactly in half along the appropriate axis, regardless of the positions of any items. Oddly placed items cannot unbalance the tree.
Deletion is much simpler (and should be faster) for the same reason: removing an item doesn't affect the division of the space, so the tree doesn't need to be rebalanced.