Kd Tree in C++

In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbour searches). k-d trees are a special case of binary space partitioning trees. More details can be found at K-d Tree.

Here is my implementation of K-d Tree based on the ruby code from Kelvin’s Domain.

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

struct Point {
	double pt[2];
	int id;
};

typedef std::vector<Point> PointList;
typedef PointList::iterator PointListItr;

struct compareX {
	bool operator ()(const Point& left, const Point& right) const {
		return left.pt[0] < right.pt[0];
	}
};
struct compareY {
	bool operator ()(const Point& left, const Point& right) const {
		return left.pt[1] < right.pt[1];
	}
};

struct kdNode {
	Point point;
	kdNode *left;
	kdNode *right;
	kdNode(PointListItr begin, PointListItr end,int depth);
};

kdNode::kdNode( PointListItr begin, PointListItr end,int depth = 0) {
	left = right = 0;
	if (begin == end){
		return ;
	}
	if( end - begin == 1) {
		point = *begin;
		return;
	}
	if(depth & 1)
		std::sort( begin, end, compareY());
	else
		std::sort( begin, end, compareX());

	PointList::size_type median = (end - begin) / 2;
	point = *(begin + median );
	if ( begin != ( begin + median ))
		left  = new kdNode(begin , begin + median , depth + 1);
	if ( (begin + median + 1 ) != end )
		right = new kdNode(begin + median + 1, end, depth + 1);
}

Point nearest(kdNode *node, Point &point, Point &min, int depth = 0) {
	if ( node ) {
		int axis = depth % 2;
		double d = point.pt[axis] - min.pt[axis];
		kdNode *near = d <= 0 ? node->left  : node->right;
		kdNode *far  = d <= 0 ? node->right : node->left;
		min = nearest(near, point, min, depth + 1);
		if ((d * d) < dist(point, min)){
			min = nearest(far, point, min, depth + 1);
		}    
		if (dist(point,node->point) < dist(point, min)) {
			min = node->point;
		}
	}
	return min;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s