quadtrees

main.cpp

// simple test run
#include "quadtree.h"

int main(){
	quadtree<int>* tree = new quadtree(rectangle(0, 0, 100, 100)); // initialize a quadtree occupying the square with size 100
	// blah blah tree->insert(integer, x, y);

	// we need to get the list of all points in a particular region
	std::list<qdatum<int>>  list = tree->to_list(region);

	// we want to map a function or a lambda onto all of the points in a particular region
std::list<qdatum<float>> float_list = tree->map<float>([](int x)->float{return (float)x;}, region);

	// or, we want to fold/reduce the tree into some accumulator through some function (http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29)
	// sum everything in some region
	int sum = 0;
	tree->fold<int>([](int i, point p, int* acc){(*acc)+=i;return acc;}, &sum, region);

	return 0;
}

quadtree.cpp

#include "quadtree.h"

#include <iostream>
using namespace std;

template<class T>
quadtree<T>* quadtree<T>::insert_(T data, point p, quadtree<T>* tree){
	if (LEAF(tree,T)){
		qleaf<T>* leaf = static_cast<qleaf<T>*>(tree);
		if (leaf->bucket.size() < leaf->threshold){
			// add item into bucket
			struct qdatum<T> q = {data, p};
			leaf->bucket.push_back(q);
			return tree;
		} else {
			// overflow, we need to resize into 4 quads
			quadtree<T>* node = new quadtree<T>(tree->bounding_box);
			// Note: as long as threshold is low compared to the density of the tree, all ops should be at log(n)
			while (!leaf->bucket.empty()){
				struct qdatum<T> cur = leaf->bucket.back();
				leaf->bucket.pop_back();
				node->insert(cur.data, cur.p);
			}
			delete leaf;
			return node;
		}
	} else {
		tree->insert(data, p);
		return tree;
	}
}

template<class T>
bool quadtree<T>::insert(T data, point p){
	//insert_(data, p, nw);
	if (nw->bounding_box.contains(p)){
		nw = insert_(data, p, nw);
	} else if (ne->bounding_box.contains(p)){
		ne = insert_(data, p, ne);
	} else if (sw->bounding_box.contains(p)){
		sw = insert_(data, p, sw);
	} else if (se->bounding_box.contains(p)){
		se = insert_(data, p, se);
	} else {
		return false; // out of bounds
	}
	return true;
}

template<class T>
bool quadtree<T>::insert(T data, int x, int y){
	point p = {x,y};
	return insert(data, p);
}

template<class T>
template<class S>
S* quadtree<T>::fold(std::function<S*(T data, point p, S*)> function, S* acc, rectangle area){
	if (!bounding_box.intersects(area)) return acc;
	if(LEAF(this, T)){
		qleaf<T>* leaf = static_cast<qleaf<T>*>(this);
		// fold over the current bucket
		list<qdatum<T>>::iterator it;
		it = leaf->bucket.begin();
		size_t i;
		for(i=0;i<leaf->bucket.size(); i++, it++){
			qdatum<T> current = *it;
			if (area.contains(current.p)){
				acc = function(current.data, current.p, acc);
			}
		}
		return acc;
	} else {
		
		acc = this->nw->fold(function, acc, area);
		acc = this->ne->fold(function, acc, area);
		acc = this->sw->fold(function, acc, area);
		acc = this->se->fold(function, acc, area);
		return acc;
	}
}

template<class T>
template<class S>
S* quadtree<T>::fold(S*(*fun)(T, point, S*), S* acc, rectangle area){
	return fold<S>([fun](T d, point p, S* a)->S*{return fun(d, p, a);}, acc, area);
}

template<class T>
template<class S>
std::list<qdatum<S>> quadtree<T>::map(std::function<S(T)> fun, rectangle area){
	std::list<qdatum<S>>* list = new std::list<qdatum<S>>();
	fold<std::list<qdatum<S>>>([fun](T d, point p, std::list<qdatum<S>>* list) -> std::list<qdatum<S>>*{
		qdatum<S> cur = {fun(d), p};
		list->push_back(cur);
		return list;
	}, list, area);

	return *list;
}

template<class T>
template<class S>
std::list<qdatum<S>> quadtree<T>::map(S(*fun)(T), rectangle area){
	return map<S>([fun](T d)->S{return fun(d);}, area);
}

template<class T>
std::list<qdatum<T>> quadtree<T>::to_list(rectangle area){
	return this->map<T>([](T d)->T{return d;}, area);
}

template<class T>
std::list<qdatum<T>> quadtree<T>::to_list(){
	return to_list(bounding_box);
}

quadtree.h

#ifndef QUADTREE_H
#define QUADTREE_H

#include <list>
#include <functional>

typedef struct point{
	int x,y;
} point;


template<class T>
struct qdatum{
	T data;
	point p;
};

class rectangle{
public:
	int x1, y1, x2, y2;
	rectangle(){};
	rectangle(int x1, int y1, int x2, int y2) : 
		x1(x1), y1(y1), x2(x2), y2(y2){};
	rectangle(point begin, point end) :
		x1(begin.x), y1(begin.y), x2(end.x), y2(end.y){};

#define avg(a,b) (((a)+(b))/2)

	inline rectangle nw(){return rectangle(x1, avg(y1,y2), avg(x1,x2), y2);}
	inline rectangle ne(){return rectangle(avg(x1,x2), avg(y1,y2), x2, y2);}
	inline rectangle se(){return rectangle(avg(x1,x2), y1, x2, avg(y1,y2));}
	inline rectangle sw(){return rectangle(x1, y1, avg(x1,x2), avg(y1,y2));}

#undef avg

	inline bool contains(int x, int y){ return x1 <= x && x <= x2 && y1 <= y && y <= y2; }
	bool contains(point p){ return contains(p.x, p.y); }

	bool intersects(rectangle other){
#define interval_intersects(x1, x2, y1, y2) ((x1 <= y1 && y1 <= x2) || (y1 <= x1 && x1 <= y2))
		return (interval_intersects(x1, x2, other.x1, other.x2)) &&
			(interval_intersects(y1, y2, other.y1, other.y2));
#undef interval_intersects
	}

	void extend(int x, int y){
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
		x1 = min(x,x1);
		y1 = min(y,y1);
		x2 = max(x,x2);
		y2 = max(y,y2);
#undef max
#undef min
	}
};

template<class T>
class quadtree{
public:
	// four quadrants
	rectangle bounding_box;
	
	quadtree(rectangle& box){
		bounding_box = box;
		nw = new qleaf<T>(box.nw());
		ne = new qleaf<T>(box.ne());
		sw = new qleaf<T>(box.sw()); 
		se = new qleaf<T>(box.se());}

	bool insert(T, point);
	bool insert(T, int, int);

	template<class S>
	S* fold(S*(*)(T, point, S*), S*, rectangle);
	template<class S>
	S* fold(std::function<S*(T data, point p, S*)>, S*, rectangle);
	template<class S>
	std::list<qdatum<S>> map(S(*)(T), rectangle area);
	template<class S>
	std::list<qdatum<S>> map(std::function<S(T)>, rectangle area);

	std::list<qdatum<T>> to_list();
	std::list<qdatum<T>> to_list(rectangle area);

	std::list<qdatum<T>> filter(std::function<bool(T, point)>, rectangle area);
	std::list<qdatum<T>> filter(bool(*)(T, point), rectangle area);

	virtual ~quadtree(){};

private:
	quadtree<T>* insert_(T, point, quadtree<T>*);
	quadtree<T> *nw, *ne, *sw, *se;

protected:
	quadtree(){};
};


template<class T>
class qleaf : public quadtree<T>{
public:
	static const int threshold = 10;
	// data and point
	std::list<struct qdatum<T>> bucket;

	qleaf(rectangle box){
		bounding_box = box;
	}

private:
	bool insert(T, point){return false;}
	bool insert(T, int, int){return false;}
};

#define LEAF(q,t) (dynamic_cast<qleaf<t>*>(q))

#endif