KdNode objects

Each KdNode has two properties:

point

The geometric location of the node as a sequence of coordinate numbers. The coordinate numbers can be floats or ints. This is an immutable property, because changing the geometric location of nodes belonging to an already built kd-tree obviously breaks subsequent search operations.

data

An arbitrary Python object connected to the location point.

KdTree objects

Each kd-tree is represented by instances of the KdTree class. Even though there are general kd-tree algorithms to add and remove nodes dynamically (see [Bentley1975]), the present implementation does not support alteration of a once built tree. This has the consequence that tree nodes must be passed to the constructor of KdTree.

A KdTree has the following (read only) properties:

dimension

The dimension of the kd-tree. This is automatically determined by the constructor.

Compilation and linkage

The header file kdtree.hpp declares the necessary structures in the namespace Gamera::Kdtree. It is installed with the other gamera header files, and can thus be included with

#include "geostructs/kdtree.hpp"
using namespace Gamera::Kdtree;

The tricky part is getting your plugin module to be linked with the actual kdtree implementation. This is achieved by adding the source file kdtree.cpp to the cpp_sources property in the plugin Python interface.

In the gamera core code, the following works:

class ExampleModule(PluginModule):
    category = "MyPlugins"
    cpp_headers = ["myplugins.hpp"]
    cpp_sources = ["gamera/src/geostructs/kdtree.cpp"]
    functions = [myplugin1, myplugin2]
module = ExampleModule()

In a toolkit, this will not work, because the path names in the cpp_sources property are relative to the location of the setup.py script. To allow for the use of the KdTree C++ class in toolkits, the source file kdtree.cpp is installed together with Gamera. You can thus specify this file in cpp_sources as follows:

class ExampleModule(PluginModule):
    # ...
    import os, sys, gamera
    gamera_root = os.path.dirname(gamera.__file__)
    cppfile = os.path.join(gamera_root,"gamera/src/geostructs/kdtree.cpp")
    if not os.path.exists(cppfile):
        gamera_root = os.path.join(sys.exec_prefix,"gamera")
        cppfile = os.path.join(gamera_root,"gamera/src/geostructs/kdtree.cpp")
    cpp_sources=[cppfile]
    # ...

Querying the installation directory is a bit tricky, because the python setuptools do not install additional data_files in a predictable way: they might go into the gamera installation directory, which can be found out through the __file__ property of the gamera module, or they might go into sys.exec_prefix/gamera (this is what the setuptools documentation says, but apparently this does not hold on all platforms).

Usage

For normal use of the kdtree, you will need the classes CoordPoint (a typedef for vector<double>), KdNode, KdNodeVector, and KdTree. Beside the property point, a KdNode can also store an arbitrary pointer as data. See the header file kdtree.hpp for details.

Here is a usage example for a nearest neighbor search:

// set points for building the tree
KdNodeVector nodes;
double points[][2] = {
  {1,4}, {2,4}, {1,5}, {3,6}, {8,9},
  {2,7}, {4,4}, {5,5}, {4,6}, {8,3},
  {-20,-20} // array terminator
};
size_t i;
for (i=0; points[i][0]>=-1.0; i++) {
  CoordPoint p;
  p.push_back(points[i][0]);
  p.push_back(points[i][1]);
  nodes.push_back(KdNode(p));
}

// build the tree
KdTree tree(&nodes);

// find the three nearest neighbors to (5,6)
KdNodeVector neighbors;
CoordPoint point(2);
point[0] = 5;
point[1] = 6;
tree.k_nearest_neighbors(point, 3, &neighbors);

If you want to restrict the returned neighbors to only those fulfilling a specific search predicate, you can define your search predicate as a callable class (aka functor, i.e. a class with the call operator operator() overwritten [Stroustrup1997]) derived from KdNodePredicate as in the following example:

// only search for nodes on the right hand side of search point
struct MyPredicate : public KdNodePredicate {
  CoordPoint point(2);
  MyPredicate(CoordPoint& p) {
    point = p;
  }
  bool operator()(const KdNode& kn) const {
    return point[0] < kn.point[0];
  }
};

The call of the class only takes a single argument, the KdNode, and returns true when this node is an admissible search result. If this criterion depends on some information from the actual search point (like its x-component in the exampel above), this information must be passed to the class constructor and stored within the class.

An instance of this class can then be passed as the third, optional argument to KdTree.k_nearest_neighbors:

KdNodeVector neighbors;
CoordPoint point(2);
point[0] = 5;
point[1] = 6;
MyPredicate predicate(point);
tree.k_nearest_neighbors(point, 3, &neighbors, &predicate);