|
// 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("�lapsed 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("�lapsed 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;
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.