kd.cpp

kd-tree c++类模板实现的演示例子. 是从国外网站上下的,结构简单,容易看懂. 文章在: http://www.codeproject.com/KB/architecture/KDT

// KD.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "KDTree.h"

KDTree<int>  Tree;

void generate_random_point(int* p, int sd)
{
	for(int k=0; k<sd; k++)
		p[k] = rand() % RMAX ;
}

void GenerateRandomTree(int nNodes)
{
	int p [SD]; // random point
	for(int n=0; n<nNodes; n++)
	{
		generate_random_point(p, SD);
		Tree.add(p);
	}
}



int main(int argc, char* argv[])
{
	Tree.GetTimerFrequency();
	Tree.StartTimer();
	GenerateRandomTree(POINTS_NUM);
	Tree.StopTimer();

	printf("KD Tree Created! \n");
	printf("Points number:\t\t%d \n", POINTS_NUM);
	printf("Tree Nodes:\t\t%d\n",Tree.nList);
	printf("Space Dimension:\t\t%d \n", SD);
	printf("Creation Time [ms]:\t%f \n", Tree.GetElapsedTime());

	printf("\nTest points:\t\t%d \n", TEST_NUM);
	
//	PrintNeighboursBrute(0);
//	return 0;

/*	int dim = 6;
	KDTreeNode<int> *L, *R, *M ;
	printf("\n------------------------------------------\n");
	M = Tree.Min(dim);
	while(M)
	{
		printf("%d\t%d", M->x[dim], M->id);
		L = M->BT_Equal[dim];
		while(L)
		{
			printf(" %d(%d)", L->id, L->x[dim]);
			L = L->BT_Next[dim];
		}
		printf("\n");
		M = M->BT_Next[dim];
	}
	return NULL;
*/	
/*	for(int n=0; n<30; n++)
	{
		L = Tree.List[n]->BT_Previous[dim];
		R = Tree.List[n]->BT_Next[dim];
		printf("ID = %d  %d < %d < %d\n",Tree.List[n]->id, !L? -1 : L->x[dim], Tree.List[n]->x[dim], !R? -1 : R->x[dim]);
	}
*/

	
	int pTarget [SD];
	int n_errors = 0;
	float dis_kd, dis_brute ;
	float kd_time, brute_time ;
	float avr_kd_time = 0;
	float avr_brute_time = 0;
	float avr_checked_nodes =0;
	int internal_error = 0;
	float avr_dis_kd=0 ;
	float avr_dis_brute=0 ;
	for(int nTest=0; nTest<TEST_NUM; nTest++)
	{
		generate_random_point(pTarget, SD);
		SetPriorityClass(GetCurrentProcess(),REALTIME_PRIORITY_CLASS);
		Tree.StartTimer();
		KDNode<int>* nearest = Tree.find_nearest(pTarget);
//		KDTreeNode<int>* nearest = Tree.find_nearest_fast(pTarget);
		Tree.StopTimer();
		SetPriorityClass(GetCurrentProcess(),NORMAL_PRIORITY_CLASS);
		kd_time = Tree.GetElapsedTime();
		dis_kd = (float)sqrt(Tree.d_min) ;
		

		SetPriorityClass(GetCurrentProcess(),REALTIME_PRIORITY_CLASS);
		Tree.StartTimer();
		KDNode<int>* nearest_brute = Tree.find_nearest_brute(pTarget);
		Tree.StopTimer();	
		SetPriorityClass(GetCurrentProcess(),NORMAL_PRIORITY_CLASS);
		brute_time = Tree.GetElapsedTime();
		dis_brute = (float)sqrt(Tree.d_min) ;

		if(!nearest || !nearest_brute)
		{
			internal_error++ ;
		}


		if(nearest && nearest_brute)
		{			
			if(nearest_brute->id != nearest->id && fabs(dis_kd - dis_brute) > 0.001)
			{
		//		nearest = Tree.find_nearest(pTarget);
				printf("\n-------------------------------------------\n");
				printf("\nKD Find Nearest Result: \n");
				if(!nearest)
				{
					printf("Search Failed! The tree is empty!");
				}
				else
				{
					printf("Point ID:\t\t%d\n",  nearest->id );
//					printf("Parent ID:\t\t%d\n",  Tree.nearest_parent->id );		
					printf("distance:\t\t%f\n",  dis_kd);
					printf("checked nodes:\t\t%d\n",  Tree.checked_nodes );
					printf("錶apsed time [ms]\t%f\n", kd_time);
				}
				printf("\nBrute Force Result : \n");	

				if(!nearest_brute)
				{
					printf("Search Failed! The tree is empty!");
				}
				else
				{
					printf("Point ID:\t\t%d\n",  nearest_brute->id );
					printf("distance:\t\t%f\n",  dis_brute);
					
					printf("錶apsed time [ms]\t%f",brute_time );
				}



				n_errors++;
			}

			avr_checked_nodes+= Tree.checked_nodes;
			avr_brute_time += brute_time ;
			avr_kd_time += kd_time ;
			avr_dis_kd += dis_kd ;
		}
	}

	avr_brute_time /= TEST_NUM;
	avr_kd_time /= TEST_NUM;
	avr_checked_nodes /= TEST_NUM ;
	avr_dis_kd /= TEST_NUM;

	printf("\n----------------------------------\n");
	printf("avr. kd time [ms]\t%f\n",avr_kd_time );
	printf("avr. check nodes\t%f\n",avr_checked_nodes );
	printf("avr. brute time [ms]\t%f\n",avr_brute_time );
	printf("kd/brute ratio\t\t%f\n",avr_brute_time/avr_kd_time );
	printf("Errors:\t\t\t%d\n",  n_errors);
	printf("Internal Errors:\t%d\n",  internal_error);
	
	return 0;
}