KD Tree implementation

kd_tree.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <memory>

using namespace std;

typedef vector<float> Point;

typedef vector<Point> PointList;

struct Comparator {

	int m_axis;

	Comparator(int axis) : m_axis(axis) {}

	bool operator() (const Point i, const Point j)
	{
		return (i[m_axis] < j[m_axis]);
	}
};

const static float pointList[7][2] = {
	{3, 4},
	{5, 6},
	{9, 1},
	{1, 6},
	{20, 5},
	{7, 300},
	{9, 8}
};

/**
  KDTree

  Partitions space by median
*/
struct KDTree {
	Point point;
	const KDTree * left;
	const KDTree * right;
};

KDTree* kd_tree( 
	const PointList::iterator begin, 
	const PointList::iterator end, 
	const int depth, 
	const size_t numPoints)
{

	const auto axis = depth % 2;

	const Comparator comparator(axis);

	std::sort (begin, end, comparator);

	const auto c = numPoints / 2;

	auto tree = new KDTree();
	tree->point = *(begin + c);

	if (c > 0) {
		tree->left = kd_tree( begin, begin + c - 1, depth + 1, c );
		tree->right = kd_tree( begin + c + 1, end, depth + 1, c);
	}

	return tree;

}


int main()
{

	auto v = std::vector<Point>();

	for (int i = 0; i < 7; ++i)
	{
		auto a = { pointList[i][0], pointList[i][1] };
		v.push_back(a);
	}

	auto mytree = kd_tree(v.begin(), v.end(), 0, v.size());

	cout << "Hello World!" << endl;
	return 0;
}