Go to the documentation of this file.
11 #include <sys/resource.h>
13 #include <DNN/ANN_C.h>
19 double _point[38][8]={
20 {-1.262280,2.039516,-1.241662,-1.121883,1.464420,-2.198507,1.457702,-1.109374 },
21 {-1.237220,1.936589,-1.034433,-1.362698,1.509152,-2.025385,1.470437,-1.237948 },
22 {-1.013849,1.950820,-1.295149,-1.183568,1.455763,-2.055501,1.515250,-1.356307 },
23 {-1.482196,2.007648,-0.996732,-1.283119,1.534123,-2.183768,1.385654,-0.987308 },
24 {-1.500418,2.097868,-1.220372,-1.033085,1.478405,-2.344629,1.351986,-0.864703 },
25 {-1.058694,2.038497,-1.494067,-0.945908,1.372108,-2.234390,1.524408,-1.210050 },
26 {-0.798914,1.929518,-1.574707,-0.976722,1.373544,-2.116169,1.558028,-1.453671 },
27 {-0.945818,2.037145,-1.752772,-0.721324,1.236064,-2.330143,1.579138,-1.212565 },
28 {-1.271433,2.116328,-1.528064,-0.812196,1.331857,-2.393527,1.459837,-0.966149 },
29 {-1.741267,2.010276,-0.887950,-1.279929,1.584056,-2.287866,1.257626,-0.759013 },
30 {-1.501615,1.884796,-0.762412,-1.528952,1.543581,-2.035084,1.412669,-1.072706 },
31 {-1.264555,1.811661,-0.803575,-1.606490,1.510936,-1.867359,1.477011,-1.320378 },
32 {-1.003100,1.834422,-1.071949,-1.441231,1.496033,-1.862884,1.501577,-1.483956 },
33 {-1.645768,2.140992,-1.346015,-0.834454,1.431947,-2.503390,1.247494,-0.654193 },
34 {-0.772193,1.827176,-1.340938,-1.248031,1.463509,-1.909529,1.518583,-1.600614 },
35 {-1.170367,2.110745,-1.780438,-0.590770,1.168126,-2.476101,1.524563,-0.960380 },
36 {-1.443594,2.150651,-1.626567,-0.630068,1.254252,-2.545875,1.376031,-0.740363 },
37 {-0.772232,1.705545,-1.111414,-1.513798,1.491066,-1.702485,1.482258,-1.724730 },
38 {-1.019783,1.707103,-0.855377,-1.681259,1.484966,-1.688372,1.489860,-1.578979 },
39 {-0.534333,1.802012,-1.741788,-0.900786,1.350070,-2.073238,1.555067,-1.650844 },
40 {-1.760679,1.875779,-0.639120,-1.535263,1.580386,-2.148980,1.310228,-0.841421 },
41 {-1.495381,1.733306,-0.544721,-1.760710,1.500579,-1.881177,1.453162,-1.170318 },
42 {-1.810300,2.087329,-1.079026,-1.044453,1.559473,-2.440484,1.162465,-0.600172 },
43 {-1.984806,1.987968,-0.813940,-1.252543,1.641118,-2.384327,1.089403,-0.526641 },
44 {-1.697993,2.147238,-1.551797,-0.593581,1.306569,-2.632096,1.192044,-0.503621 },
45 {-1.880391,2.122402,-1.298290,-0.781258,1.482256,-2.588584,1.056138,-0.421648 },
46 {-0.928724,2.033960,-1.978375,-0.483489,1.057093,-2.442046,1.627235,-1.132694 },
47 {-0.681670,1.919328,-1.901170,-0.672762,1.202390,-2.265498,1.618211,-1.428134 },
48 {-1.256384,1.658986,-0.596002,-1.835289,1.462431,-1.699324,1.492230,-1.425470 },
49 {-0.543469,1.673458,-1.361725,-1.324151,1.484989,-1.760384,1.469352,-1.832039 },
50 {-1.363260,2.127833,-1.865133,-0.407814,1.059721,-2.613543,1.444583,-0.719095 },
51 {-2.039651,2.055739,-1.027143,-1.002035,1.620787,-2.517956,0.964684,-0.367795 },
52 {-2.007873,1.841635,-0.545726,-1.522485,1.626393,-2.256107,1.166803,-0.605743 },
53 {-1.780364,1.712648,-0.399743,-1.762945,1.524117,-2.026988,1.367265,-0.902002 },
54 {-1.028464,1.558295,-0.645619,-1.909291,1.426565,-1.515046,1.478929,-1.673280 },
55 {-0.795581,1.580700,-0.896500,-1.754151,1.464109,-1.517622,1.451276,-1.816512 },
56 {-1.643063,1.578628,-0.275135,-1.936803,1.435267,-1.851053,1.461556,-1.088357 },
57 {-0.538870,1.554160,-1.151812,-1.573927,1.493638,-1.553494,1.414819,-1.951598 }
60 double _q[8]={-0.419985,1.755759,-1.993156,-0.661874,1.224372,-2.184798,1.589697,-1.651615 };
82 #define POINTS_ON_SPHERE 0
89 #define N_POINTS 50000
103 #define TOPOLOGY TOPOLOGY_S
110 #define POINTS_IN_LEAF 25
119 #define SAMPLING_EXPANSION 1.0
156 int CmpUInt( const void *a, const void *b);
172 return(*(( unsigned int*)a)-*(( unsigned int*)b));
179 getrusage(RUSAGE_SELF,&usage);
182 return(( double)(usage.ru_utime.tv_sec +usage.ru_stime.tv_sec )*1000.0+
183 ( double)(usage.ru_utime.tv_usec+usage.ru_stime.tv_usec)/1000.0);
210 char *option[ N_OPTIONS]={ "-h", "-n", "-d", "-t", "-l", "-r", "-m", "-s", "-e"};
212 unsigned int nPoints,dim,tpg,pLeaf,rep;
213 double searchR,expansion;
226 unsigned int *topology;
229 unsigned int *nn,n,m;
257 if (strcmp(arg[i],option[j])==0)
262 fprintf(stderr, "cuik-kdtree test program\n");
263 fprintf(stderr, "Usage: \n");
264 fprintf(stderr, " test-cuik-kdtree <option> <ooption> <option> ...\n");
265 fprintf(stderr, "Options: \n");
266 fprintf(stderr, " -n <value> Number of random points to generate.\n");
267 fprintf(stderr, " Default value: %u\n", N_POINTS);
268 fprintf(stderr, " -d <value> Dimension of the points to generate.\n");
269 fprintf(stderr, " Default value: %u\n", DIM);
270 fprintf(stderr, " -t <R|S> Topology (R or S) of the points to generate.\n");
271 fprintf(stderr, " The same topology is used for all the dimensions.\n");
273 fprintf(stderr, " -l <value> Maximum number of points in each leaf.\n");
275 fprintf(stderr, " -r <value> Search radius (for the in-ball queries).\n");
276 fprintf(stderr, " Default value: %f\n", R);
277 fprintf(stderr, " -m <value> Number of reptetions to gather execution times.\n");
278 fprintf(stderr, " Default value: %u\n", REP);
279 fprintf(stderr, " -e <value> Sampling expansion (not used so far in the test).\n");
281 fprintf(stderr, " -s <value> Random seed.\n");
282 fprintf(stderr, " Default value: arbitrarily fixed\n");
283 fprintf(stderr, " -h This help.\n");
284 fprintf(stderr, "Examples: \n");
285 fprintf(stderr, " test-cuik-kdtree\n");
286 fprintf(stderr, " test-cuik-kdtree -t R -r 0.75\n");
287 fprintf(stderr, " test-cuik-kdtree -n 100000\n");
294 nPoints=( unsigned int)atoi(arg[i]);
297 fprintf(stderr, "Too smalll number of points (-n).\n");
305 dim=( unsigned int)atoi(arg[i]);
308 fprintf(stderr, "Too smalll dimension (-d).\n");
325 fprintf(stderr, "Unknown topology (-t).\n");
334 pLeaf=( unsigned int)atoi(arg[i]);
337 fprintf(stderr, "Too smalll number of points in each leaf (-l).\n");
345 searchR=(double)atof(arg[i]);
348 fprintf(stderr, "The search radius must be positive (-r).\n");
356 rep=( unsigned int)atoi(arg[i]);
359 fprintf(stderr, "The number of repetitions must be positive (-m).\n");
367 ri=( unsigned int)atof(arg[i]);
373 expansion=atof(arg[i]);
382 fprintf(stderr, "Unknown command line option %s.\nUse -h for help.\n",arg[i]);
402 printf( "\n\n************************************************************\n");
403 printf( "Parameters\n");
404 printf( " Random seed : %u\n",ri);
405 printf( " Topology : %s\n",(tpg== TOPOLOGY_R? "R": "S"));
406 printf( " No. points : %u\n",nPoints);
407 printf( " Dimension : %u\n",dim);
408 printf( " Points in leaf: %u\n",pLeaf);
409 printf( " Search radius : %f\n",searchR);
411 printf( " Repetitions : %u\n",rep);
427 NEW(topology,dim, unsigned int);
438 printf( "Generating %u random points\n\n",nPoints);
440 NEW(point,nPoints, double*);
441 for(i=0;i<nPoints;i++)
443 NEW(point[i],dim, double);
444 #if (POINTS_ON_SPHERE)
451 point[i][j]=_point[i][j];
459 printf( "Building kd-tree\n");
463 Ykdt=CreateKDTree(dim);
465 Ykdt=CreateKDTreeT(dim,( int *)topology);
466 for(i=0;i<nPoints;i++)
467 AddPoint2KDTree(point[i],Ykdt);
469 printf( " MPNN : %7.3f ms\n",tEnd-tStart);
470 printf( " MPNN x point: %7.3f ms\n",(tEnd-tStart)/( double)nPoints);
474 for(i=0;i<nPoints;i++)
477 Mkdt= InitKDTree(&ambient,topology,pLeaf,expansion,1,&(point[i]),&i);
482 printf( " Cuik : %7.3f ms\n",tEnd-tStart);
483 printf( " Cuik x point: %7.3f ms\n\n",(tEnd-tStart)/( double)nPoints);
494 printf( "Defining the query point\n\n");
505 printf( "Searching NN\n");
506 printf( " MPNN kd-tree : ");
507 QueryKDTree(q,( int *)& id,&d,Ykdt);
511 printf( " Cuik kd-tree : ");
515 printf( " Brute-force search: ");
517 for(i=0;i<nPoints;i++)
526 printf( "%u\n\n",idMin);
528 printf( "Searching in-ball\n");
530 printf( " MPNN kd-tree : ");
531 QueryKDTreeR(q,searchR,( int *)(&n),( int **)(&nn),&dst,Ykdt);
534 qsort(nn,n, sizeof( unsigned int), CmpUInt);
560 printf( " Cuik kd-tree : ");
564 qsort(nn,n, sizeof( unsigned int), CmpUInt);
586 printf( " Brute-force search: ");
590 NEW(nn,m, unsigned int);
591 for(i=0;i<nPoints;i++)
626 printf( "Average time per NN query\n");
633 QueryKDTree(q,( int *)& id,&d,Ykdt);
636 printf( " MPNN : %f ms\n",(tEnd-tStart)/( double)rep);
646 printf( " Cuik : %f ms\n",(tEnd-tStart)/( double)rep);
652 for(i=0;i<nPoints;i++)
663 printf( " Brute-force: %f ms\n\n",(tEnd-tStart)/( double)rep);
665 printf( "Average time per in-ball query\n");
672 QueryKDTreeR(q,searchR,( int *)(&n),( int **)(&nn),&dst,Ykdt);
680 printf( " MPNN : %f ms\n",(tEnd-tStart)/( double)rep);
692 printf( " Cuik : %f ms\n",(tEnd-tStart)/( double)rep);
700 NEW(nn,m, unsigned int);
701 for(i=0;i<nPoints;i++)
714 printf( " Brute force: %f ms\n\n",(tEnd-tStart)/( double)rep);
720 for(i=0;i<nPoints;i++)
733 return(EXIT_SUCCESS);
#define N_OPTIONS Number of command line options.
#define POINTS_IN_LEAF Maximum number of points in a leaf.
void RandomPointInRectangle(double *c, Trectangle *b) Returns the a random point along the selected dimensions.
#define TOPOLOGY Topology.
void VectorNormalize(unsigned int s, double *v) Normalizes a vector.
double randomNormal() Returns a random double acording to a normal distribution.
void PlotKDtree(char *fname, boolean sphere, TKDtree *kdt) Plots a kd-tree.
void SetRectangleLowerLimit(unsigned int i, double l, Trectangle *b) Set the lower limit.
#define N_POINTS Number of points.
void DeleteRectangle(Trectangle *b) Destructor.
void DeleteKDtree(TKDtree *kdt) Deletes a KD-tree.
#define REP Number of queries.
double getTime() Gets the time in miliseconds.
#define TOPOLOGY_R One of the possible topologies.
#define NEW(_var, _n, _type) Allocates memory space.
#define POINTS_ON_SPHERE Method to generate the random points.
Definition of constants and macros used in several parts of the library.
Headers of the kd-tree implementation.
#define SAMPLING_EXPANSION Sampling area expansion.
void SetRectangleUpperLimit(unsigned int i, double u, Trectangle *b) Set the upper limit.
void InitRectangle(unsigned int dim, double *l, double *u, Trectangle *b) Initializes a rectangle.
double VectorSquaredDistanceTopologyMin(double t2, unsigned int s, unsigned int *tp, double *v1, double *v2) Computes the squared distance of two points.
#define TOPOLOGY_S One of the possible topologies.
Definition of basic operations between points.
int main(int argc, char **arg) Main body of the test program for the cuik-kdtree library.
Definition of basic randomization functions.
unsigned int NearestNeighbour(double *point, TKDtree *kdt) Determines the nearest-neighbour for a point.
void NeighboursInBall(double *point, double r, unsigned int *n, unsigned int **ids, TKDtree *kdt) Neighbours in a ball.
TKDtree * InitKDTree(Trectangle *ambient, unsigned int *topology, unsigned int m, double r, unsigned int n, double **points, unsigned int *ids) Initializes a kd-tree from a set of points.
void AddPoint2KDtree(double *point, unsigned int id, TKDtree **kdt) Adds a point to a kd-tree.
#define MEM_DUP(_var, _n, _type) Duplicates a previously allocated memory space.
int CmpUInt(const void *a, const void *b) Compares two unsigned integers.
void randomSet(unsigned int seed) Sets the random seed.
|
Follow us!