kd-Tree Point Search

// visual test of kd-tree findClosestPoints()
// sean whalen
 
#include <vector>
 
#include <Vrui/Vrui.h>
#include <Vrui/Application.h>
#include <Vrui/Geometry.h>
#include <GL/GLMaterial.h>
#include <GL/GLModels.h>
#include <Geometry/ClosePointSet.h>
#include <Geometry/PointKdTree.h>
 
#define NUM_POINTS 50
#define NUM_CLOSEST_POINTS 5
 
class KDExample : public Vrui::Application
{
private:
	Geometry::ClosePointSet<Vrui::Point>* closestPointSet;
	Geometry::PointKdTree<double, 3, Vrui::Point>* pointTree;
	std::vector<Vrui::Point> pointVector;
	Vrui::Point randomPoint;
 
public:
	KDExample(int, char**, char**);
 
	void display(GLContextData&) const;
	void centerGraph();	
};
 
KDExample::KDExample(int argc, char** argv, char** appDefaults)
: Vrui::Application(argc, argv, appDefaults)
{
	closestPointSet = new Geometry::ClosePointSet<Vrui::Point>(NUM_CLOSEST_POINTS);
	pointTree = new Geometry::PointKdTree<double, 3, Vrui::Point>();	
	pointVector.resize(NUM_POINTS);
 
	for(int i = 0; i < NUM_POINTS; i++)
	{
		pointVector[i] = Vrui::Point(rand()%30, rand()%30, rand()%30);
		pointTree->insertPoint(pointVector[i]);
	}
 
	randomPoint = Vrui::Point(rand()%30, rand()%30, rand()%30);
	centerGraph();
}
 
void KDExample::centerGraph()
{
	Vrui::Point& p = pointVector[0];
	double xCenterAverage = p[0];
	double yCenterAverage = p[1];
	double zCenterAverage = p[2];
 
	// find average positions over all nodes in graph
	for(int i = 1; i < pointVector.size(); i++)
	{
		p = pointVector[i];
		xCenterAverage += (1.0/i) * (p[0] - xCenterAverage);
		yCenterAverage += (1.0/i) * (p[1] - yCenterAverage);
		zCenterAverage += (1.0/i) * (p[2] - zCenterAverage);
	}
 
	// update transform to use new center
	Vrui::setNavigationTransformation(Vrui::Point(xCenterAverage, yCenterAverage, zCenterAverage), 25.0);
}
 
void KDExample::display(GLContextData& contextData) const
{
	GLMaterial white(GLMaterial::Color(1, 1, 1));
	GLMaterial red(GLMaterial::Color(1, 0, 0));
	GLMaterial blue(GLMaterial::Color(0, 0, 1));
 
	// draw set of random points
	glMaterial(GLMaterialEnums::FRONT_AND_BACK, white);
 
	for(int i = 0; i < pointVector.size(); i++)
	{
		const Vrui::Point& p = pointVector[i];
 
		glPushMatrix();
			glTranslatef(p[0], p[1], p[2]);
			glDrawSphereMercator(0.3, 20, 20);
		glPopMatrix();
	}
 
	// draw random point	
	glMaterial(GLMaterialEnums::FRONT_AND_BACK, blue);
 
	glPushMatrix();
		glTranslatef(randomPoint[0], randomPoint[1], randomPoint[2]);
		glDrawSphereMercator(0.3, 20, 20);		
	glPopMatrix();
 
	// draw closest points to random point
	closestPointSet->clear();
	pointTree->findClosestPoints(randomPoint, *closestPointSet);
 
	glMaterial(GLMaterialEnums::FRONT_AND_BACK, red);
 
	for(int i = 0; i < closestPointSet->getNumPoints(); i++)
	{
		const Vrui::Point& q = closestPointSet->getPoint(i);
 
		glPushMatrix();
			glTranslatef(q[0], q[1], q[2]);
			glDrawSphereMercator(0.3, 20, 20);
		glPopMatrix();
	}
}
 
int main(int argc, char** argv)
{
	char** appDefaults = 0;
	KDExample app(argc, argv, appDefaults);
	app.run();
 
	return 0;	
}