kdtree implementation C++

Question

Any recommendations for a C/C++ kd-tree?

I'm looking for an existing implementation which the poster hopefully has worked with or has heard good things about. Also, I need to use this kd-tree to do a 1/2-NN search.

Answer 1

Recommend 2 approaches to consider :

1) classic ptr approach :

class KdTreeNode
{
   private :
    vector<T> data;
    KdTreeNode * Left;
    KdTreeNode * Right; 
};

2) std::map approach :

where a tree node consits of :

class KdTreeNode
{
  private :
    map<K, V> values;
    map<K, KdTreeNode> subnodes;
};

ad 1. I've been using it a couple years back in a graphics project my company needed, it's simple , and get's the job done.

ad 2. I've been using this lately, although not as a KdTree. Thanks to using maps it's very versatile.

I'm not saying my solutions are the best, I've tried both - on different ocasions - and they worked.

Hope that helps

Answer 2

http://code.google.com/p/kdtree/

Answer 3

This code is optimized for SIZE.

So you'll see a lot of "bad hacks".

Note that we used 'struct', but it can be easily changed to be a class if you add public:. Paste also missing 'Point2D' type but you can guess how it looks. Includes and Include guards also removed.

/* ------------------------------ kdtree.h ------------------------------ */

typedef struct kdNode2D
{
 kdNode2D(pPoint2D pointList, int pointLength, int depth = 0);

 ~kdNode2D()
 {
  for(int i=0; i<2; ++i)
   delete sons[i];
 }

 /* Leave depth alone for outside code! */
 unsigned nearest(const Point2D &point, int depth = 0);

 union {
  struct {
   kdNode2D* left;
   kdNode2D* right;
  };

  kdNode2D* sons[2];
 };

 Point2D p;

} kdNode2D;

/* ----------------------------- kdtree.cpp ----------------------------- */

static int cmpX(const void* a, const void* b)
{
 return (*(pPoint2D)a).x - (*(pPoint2D)b).x;
}

static int cmpY(const void* a, const void* b)
{
 return (*(pPoint2D)a).y - (*(pPoint2D)b).y;
}

kdNode2D::kdNode2D(pPoint2D pointList, int pointLength, int depth)
{
 if(pointLength == 1) {
  left = NULL;
  right = NULL;
  p  = *pointList;
  return;
 }

  // Odd depth = Y, even depth = X
 if(depth & 1)
  qsort(pointList, pointLength, sizeof(Point2D), cmpY);
 else
  qsort(pointList, pointLength, sizeof(Point2D), cmpX);

 const int halfLength = pointLength >> 1;
 p = pointList[halfLength];
 for(int i=0; i<2; ++i)
  sons[i] = new kdNode2D(pointList + (i*halfLength), halfLength, depth + 1);
}

unsigned kdNode2D::nearest(const Point2D &point, int depth)
{
 /* End of tree. */
 if(!left || !right)   // We assume if left != NULL, then right != NULL (see ctor)
 {
  Point2D r = p;
  for(int i=0; i<2; ++i)
   r[i] -= point[i];

  return r.dot(r);
 }

 const int tmp = p[depth] - point[depth];
 const int side = tmp < 0; /* Prefer the left. */

 /* Switch depth. */
 depth ^= 1;

 /* Search the near side of the tree. */
 int leftDist = sons[side]->nearest(point, depth);

 /* Radius intersects a kd tree boundary? */
 if(leftDist < (tmp * tmp))
 {
  /* No; this is the nearest point on this side. */
  return leftDist;
 }

 /* Yes; look at the points on the other side. */
 return min(leftDist, sons[side ^ 1]->nearest(point, depth));
}

Answer 4

http://people.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN

Or OpenCV 1.2 which has FLANN.

Answer 5

could you include pPoint2D definition?