kdtree.hpp File Reference

Defines the interface for the KDTree class. More...

#include <vector>
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cassert>
#include "function.hpp"
#include "allocator.hpp"
#include "iterator.hpp"
#include "node.hpp"
#include "region.hpp"

Include dependency graph for kdtree.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	kd_tree::KDTree< __K, _Val, _Acc, _Dist, _Cmp, _Alloc >

Macros
#define	KDTREE_VERSION   700
#define	KDTREE_LIB_VERSION   "0_7_0"

Detailed Description

Defines the interface for the KDTree class.

Author

Martin F. Krafft libkd.nosp@m.tree.nosp@m.@pobo.nosp@m.x.ma.nosp@m.dduck.nosp@m..net

Paul Harris figured this stuff out (below) Notes: This is similar to a binary tree, but its not the same. There are a few important differences:

• Each level is sorted by a different criteria (this is fundamental to the design).

• It is possible to have children IDENTICAL to its parent in BOTH branches This is different to a binary tree, where identical children are always to the right So, KDTree has the relationships:

  • The left branch is <= its parent (in binary tree, this relationship is a plain < )
  • The right branch is <= its parent (same as binary tree)

  This is done for mostly for performance. Its a LOT easier to maintain a consistent tree if we use the <= relationship. Note that this relationship only makes a difference when searching for an exact item with find() or find_exact, other search, erase and insert functions don't notice the difference.

  In the case of binary trees, you can safely assume that the next identical item will be the child leaf, but in the case of KDTree, the next identical item might be a long way down a subtree, because of the various different sort criteria.

  So erase()ing a node from a KDTree could require serious and complicated tree rebalancing to maintain consistency... IF we required binary-tree-like relationships.

  This has no effect on insert()s, a < test is good enough to keep consistency.

  It has an effect on find() searches:

  • Instead of using compare(child,node) for a < relationship and following 1 branch, we must use !compare(node,child) for a <= relationship, and test BOTH branches, as we could potentially go down both branches.

  It has no real effect on bounds-based searches (like find_nearest, find_within_range) as it compares vs a boundary and would follow both branches if required.

  This has no real effect on erase()s, a < test is good enough to keep consistency.