ROOT  6.07/01
Reference Guide
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
kDTreeTest.cxx
Go to the documentation of this file.
1 /*
2  Test macro for TKDTree
3 
4  TestBuild(); // test build function of kdTree for memory leaks
5  TestSpeed(); // test the CPU consumption to build kdTree
6  TestkdtreeIF(); // test functionality of the kdTree
7  TestSizeIF(); // test the size of kdtree - search application - Alice TPC tracker situation
8  //
9 */
10 
11 //#include <malloc.h>
12 #include "TSystem.h"
13 #include "TMatrixD.h"
14 #include "TRandom.h"
15 #include "TGraph.h"
16 #include "TStopwatch.h"
17 #include "TKDTree.h"
18 #include "TApplication.h"
19 #include "TCanvas.h"
20 #include <iostream>
21 
22 
23 bool showGraphics = false;
24 
25 
26 void TestBuild(const Int_t npoints = 1000000, const Int_t bsize = 100);
27 void TestConstr(const Int_t npoints = 1000000, const Int_t bsize = 100);
28 void TestSpeed(Int_t npower2 = 20, Int_t bsize = 10);
29 
30 //void TestkdtreeIF(Int_t npoints=1000, Int_t bsize=9, Int_t nloop=1000, Int_t mode = 2);
31 //void TestSizeIF(Int_t nsec=36, Int_t nrows=159, Int_t npoints=1000, Int_t bsize=10, Int_t mode=1);
32 
33 
34 
36 {
37  // get mem info
38  ProcInfo_t procInfo;
39  gSystem->GetProcInfo(&procInfo);
40  return procInfo.fMemVirtual;
41 }
42 
43 ////////////////////////////////////////////////////////////////////////////////
44 ///
45 ///
46 ///
47 
48 void kDTreeTest()
49 {
50  printf("\n\tTesting kDTree memory usage ...\n");
51  TestBuild();
52  printf("\n\tTesting kDTree speed ...\n");
53  TestSpeed();
54 }
55 
56 ////////////////////////////////////////////////////////////////////////////////
57 ///
58 /// Test kdTree for memory leaks
59 ///
60 
61 void TestBuild(const Int_t npoints, const Int_t bsize){
62  Float_t *data0 = new Float_t[npoints*2];
63  Float_t *data[2];
64  data[0] = &data0[0];
65  data[1] = &data0[npoints];
66  for (Int_t i=0;i<npoints;i++) {
67  data[1][i]= gRandom->Rndm();
68  data[0][i]= gRandom->Rndm();
69  }
70  Float_t before =Mem();
71  TKDTreeIF *kdtree = new TKDTreeIF(npoints, 2, bsize, data);
72  kdtree->Build();
73  Float_t after = Mem();
74  printf("Memory usage %f KB\n",after-before);
75  delete kdtree;
76  Float_t end = Mem();
77  printf("Memory leak %f KB\n", end-before);
78  delete[] data0;
79  return;
80 }
81 
82 ////////////////////////////////////////////////////////////////////////////////
83 ///This is not really a test, it's a function that illustrates the internal
84 ///behaviour of the kd-tree.
85 ///
86 ///Print out the internal kd-tree data-members, like fCrossNode, for
87 ///better understading
88 
90 {
91 
92  TKDTreeIF *kdtree = 0x0;
93  Int_t npoints = 33;
94  Int_t bsize = 10;
95  Float_t *data0 = new Float_t[200]; //not to reallocate each time
96  Float_t *data1 = new Float_t[200];
97  for (Int_t i=0;i<npoints;i++) {
98  data0[i]= gRandom->Rndm();
99  data1[i]= gRandom->Rndm();
100  }
101 
102  kdtree = new TKDTreeIF(npoints, 2, bsize);
103  kdtree->SetData(0, data0);
104  kdtree->SetData(1, data1);
105  kdtree->Build();
106 
107  printf("fNNodes %d, fRowT0 %d, fCrossNode %d, fOffset %d\n",kdtree->GetNNodes(), kdtree->GetRowT0(), kdtree->GetCrossNode(), kdtree->GetOffset());
108  delete kdtree;
109  npoints = 44;
110  for (Int_t i=0;i<npoints;i++) {
111  data0[i]= gRandom->Rndm();
112  data1[i]= gRandom->Rndm();
113  }
114  kdtree = new TKDTreeIF(npoints, 2, bsize);
115  kdtree->SetData(0, data0);
116  kdtree->SetData(1, data1);
117  kdtree->Build();
118 
119  printf("fNNodes %d, fRowT0 %d, fCrossNode %d, fOffset %d\n",kdtree->GetNNodes(), kdtree->GetRowT0(), kdtree->GetCrossNode(), kdtree->GetOffset());
120  delete kdtree;
121  npoints = 55;
122  for (Int_t i=0;i<npoints;i++) {
123  data0[i]= gRandom->Rndm();
124  data1[i]= gRandom->Rndm();
125  }
126  kdtree = new TKDTreeIF(npoints, 2, bsize);
127  kdtree->SetData(0, data0);
128  kdtree->SetData(1, data1);
129  kdtree->Build();
130 
131  printf("fNNodes %d, fRowT0 %d, fCrossNode %d, fOffset %d\n",kdtree->GetNNodes(), kdtree->GetRowT0(), kdtree->GetCrossNode(), kdtree->GetOffset());
132  delete kdtree;
133  npoints = 66;
134  for (Int_t i=0;i<npoints;i++) {
135  data0[i]= gRandom->Rndm();
136  data1[i]= gRandom->Rndm();
137  }
138  kdtree = new TKDTreeIF(npoints, 2, bsize);
139  kdtree->SetData(0, data0);
140  kdtree->SetData(1, data1);
141  kdtree->Build();
142 
143  printf("fNNodes %d, fRowT0 %d, fCrossNode %d, fOffset %d\n",kdtree->GetNNodes(), kdtree->GetRowT0(), kdtree->GetCrossNode(), kdtree->GetOffset());
144  delete kdtree;
145  npoints = 77;
146  for (Int_t i=0;i<npoints;i++) {
147  data0[i]= gRandom->Rndm();
148  data1[i]= gRandom->Rndm();
149  }
150  kdtree = new TKDTreeIF(npoints, 2, bsize);
151  kdtree->SetData(0, data0);
152  kdtree->SetData(1, data1);
153  kdtree->Build();
154 
155  printf("fNNodes %d, fRowT0 %d, fCrossNode %d, fOffset %d\n",kdtree->GetNNodes(), kdtree->GetRowT0(), kdtree->GetCrossNode(), kdtree->GetOffset());
156  delete kdtree;
157  npoints = 88;
158  for (Int_t i=0;i<npoints;i++) {
159  data0[i]= gRandom->Rndm();
160  data1[i]= gRandom->Rndm();
161  }
162  kdtree = new TKDTreeIF(npoints, 2, bsize);
163  kdtree->SetData(0, data0);
164  kdtree->SetData(1, data1);
165  kdtree->Build();
166 
167  printf("fNNodes %d, fRowT0 %d, fCrossNode %d, fOffset %d\n",kdtree->GetNNodes(), kdtree->GetRowT0(), kdtree->GetCrossNode(), kdtree->GetOffset());
168  delete kdtree;
169 
170 
171 
172  delete[] data0;
173  delete[] data1;
174 }
175 
176 
177 
178 ////////////////////////////////////////////////////////////////////////////////
179 ///
180 ///compare the results of different data setting functions
181 ///nothing printed - all works correctly
182 
183 void TestConstr(const Int_t npoints, const Int_t bsize)
184 {
185  Float_t *data0 = new Float_t[npoints*2];
186  Float_t *data[2];
187  data[0] = &data0[0];
188  data[1] = &data0[npoints];
189  for (Int_t i=0;i<npoints;i++) {
190  data[1][i]= gRandom->Rndm();
191  data[0][i]= gRandom->Rndm();
192  }
193  Float_t before =Mem();
194  TKDTreeIF *kdtree1 = new TKDTreeIF(npoints, 2, bsize, data);
195  kdtree1->Build();
196  TKDTreeIF *kdtree2 = new TKDTreeIF(npoints, 2, bsize);
197  kdtree2->SetData(0, data[0]);
198  kdtree2->SetData(1, data[1]);
199  kdtree2->Build();
200  Int_t nnodes = kdtree1->GetNNodes();
201  if (nnodes - kdtree2->GetNNodes()>1){
202  printf("different number of nodes\n");
203  return;
204  }
205  for (Int_t inode=0; inode<nnodes; inode++){
206  Float_t value1 = kdtree1->GetNodeValue(inode);
207  Float_t value2 = kdtree2->GetNodeValue(inode);
208  if (TMath::Abs(value1-value2 > 0.001)){
209  printf("node %d value: %f %f\n", inode, kdtree1->GetNodeValue(inode), kdtree2->GetNodeValue(inode));
210  }
211  }
212  delete kdtree1;
213  delete kdtree2;
214  Float_t end = Mem();
215  printf("Memory leak %f KB\n", end-before);
216  delete[] data0;
217  return;
218 }
219 
220 
221 ////////////////////////////////////////////////////////////////////////////////
222 ///
223 /// Test of building time of kdTree
224 ///
225 
226 void TestSpeed(Int_t npower2, Int_t bsize)
227 {
228  if(npower2 < 10){
229  printf("Please specify a power of 2 greater than 10\n");
230  return;
231  }
232 
233  Int_t npoints = Int_t(pow(2., npower2))*bsize;
234  Float_t *data0 = new Float_t[npoints*2];
235  Float_t *data[2];
236  data[0] = &data0[0];
237  data[1] = &data0[npoints];
238  for (Int_t i=0;i<npoints;i++) {
239  data[1][i]= gRandom->Rndm();
240  data[0][i]= gRandom->Rndm();
241  }
242 
243  TGraph *g = new TGraph(npower2-10);
244  g->SetMarkerStyle(7);
246  Int_t tpoints;
247  TKDTreeIF *kdtree = 0x0;
248  for(int i=10; i<npower2; i++){
249  tpoints = Int_t(pow(2., i))*bsize;
250  timer.Start(kTRUE);
251  kdtree = new TKDTreeIF(tpoints, 2, bsize, data);
252  kdtree->Build();
253  timer.Stop();
254  g->SetPoint(i-10, i, timer.CpuTime());
255  printf("npoints [%d] nodes [%d] cpu time %f [s]\n", tpoints, kdtree->GetNNodes(), timer.CpuTime());
256  //timer.Print("u");
257  delete kdtree;
258  }
259  if (showGraphics) {
260  g->Draw("apl");
261  gPad->Update();
262  }
263 
264  delete[] data0;
265  return;
266 }
267 
268 /*
269 ////////////////////////////////////////////////////////////////////////////////
270 ///
271 /// Test size to build kdtree
272 ///
273 
274 void TestSizeIF(Int_t nsec, Int_t nrows, Int_t npoints, Int_t bsize, Int_t mode)
275 {
276  Float_t before =Mem();
277  for (Int_t isec=0; isec<nsec;isec++)
278  for (Int_t irow=0;irow<nrows;irow++){
279  TestkdtreeIF(npoints,1,mode,bsize);
280  }
281  Float_t after = Mem();
282  printf("Memory usage %f\n",after-before);
283 }
284 */
285 
286 /*
287 ////////////////////////////////////////////////////////////////////////////////
288 ///
289 /// Test speed and functionality of 2D kdtree.
290 /// Input parametrs:
291 /// npoints - number of data points
292 /// bsize - bucket size
293 /// nloop - number of loops
294 /// mode - tasks to be performed by the kdTree
295 /// - 0 : time building the tree
296 ///
297 
298 void TestkdtreeIF(Int_t npoints, Int_t bsize, Int_t nloop, Int_t mode)
299 {
300 
301  Float_t rangey = 100;
302  Float_t rangez = 100;
303  Float_t drangey = 0.1;
304  Float_t drangez = 0.1;
305 
306  //
307  Float_t *data0 = new Float_t[npoints*2];
308  Float_t *data[2];
309  data[0] = &data0[0];
310  data[1] = &data0[npoints];
311  //Int_t i;
312  for (Int_t i=0; i<npoints; i++){
313  data[0][i] = gRandom->Uniform(-rangey, rangey);
314  data[1][i] = gRandom->Uniform(-rangez, rangez);
315  }
316  TStopwatch timer;
317 
318  // check time build
319  printf("building kdTree ...\n");
320  timer.Start(kTRUE);
321  TKDTreeIF *kdtree = new TKDTreeIF(npoints, 2, bsize, data);
322  kdtree->Build();
323  timer.Stop();
324  timer.Print();
325  if(mode == 0) return;
326 
327  Float_t countern=0;
328  Float_t counteriter = 0;
329  Float_t counterfound = 0;
330 
331  if (mode ==2){
332  if (nloop) timer.Start(kTRUE);
333  Int_t *res = new Int_t[npoints];
334  Int_t nfound = 0;
335  for (Int_t kloop = 0;kloop<nloop;kloop++){
336  if (kloop==0){
337  counteriter = 0;
338  counterfound= 0;
339  countern = 0;
340  }
341  for (Int_t i=0;i<npoints;i++){
342  Float_t point[2]={data[0][i],data[1][i]};
343  Float_t delta[2]={drangey,drangez};
344  Int_t iter =0;
345  nfound =0;
346  Int_t bnode =0;
347  //kdtree->FindBNode(point,delta, bnode);
348  //continue;
349  kdtree->FindInRangeA(point,delta,res,nfound,iter,bnode);
350  if (kloop==0){
351  //Bool_t isOK = kTRUE;
352  Bool_t isOK = kFALSE;
353  for (Int_t ipoint=0;ipoint<nfound;ipoint++)
354  if (res[ipoint]==i) isOK =kTRUE;
355  counteriter+=iter;
356  counterfound+=nfound;
357  if (isOK) {
358  countern++;
359  }else{
360  printf("Bug\n");
361  }
362  }
363  }
364  }
365 
366  if (nloop){
367  timer.Stop();
368  timer.Print();
369  }
370 
371  delete [] res;
372  }
373  delete [] data0;
374 
375  counteriter/=npoints;
376  counterfound/=npoints;
377  if (nloop) printf("Find nearest point:\t%f\t%f\t%f\n",countern, counteriter, counterfound);
378 }
379 */
380 
381 ////////////////////////////////////////////////////////////////////////////////
382 ///Test TKDTree::FindNearestNeighbors() function
383 
385 {
386 //Generate some 3d points
387  Int_t npoints = 10000;
388  Int_t nn = 100;
389  Int_t ntimes = 100;
390  Int_t bsize = 10; //bucket size of the kd-tree
391 
392  Double_t *x = new Double_t[npoints];
393  Double_t *y = new Double_t[npoints];
394  Double_t *z = new Double_t[npoints];
395  for (Int_t i=0; i<npoints; i++){
396  x[i] = gRandom->Uniform(-100, 100);
397  y[i] = gRandom->Uniform(-100, 100);
398  z[i] = gRandom->Uniform(-100, 100);
399  }
400 
401  Int_t diff1=0;
402 
403 //for the distances brute-force:
404  Double_t *dist = new Double_t[npoints];
405  Int_t *index = new Int_t[npoints];
406 
407 //Build the tree
408  TKDTreeID *kdtree = new TKDTreeID(npoints, 3, bsize);
409  kdtree->SetData(0, x);
410  kdtree->SetData(1, y);
411  kdtree->SetData(2, z);
412  kdtree->Build();
413  Int_t *index2 = new Int_t[nn];
414  Double_t *dist2 = new Double_t[nn];
415  Double_t point[3];
416 //Select a random point
417  for (Int_t itime=0; itime<ntimes; itime++){
418  Int_t ipoint = Int_t(gRandom->Uniform(0, npoints));
419 
420  for (Int_t i=0; i<npoints; i++){
421  dist[i]=0;
422 
423  dist[i]+=(x[i]-x[ipoint])*(x[i]-x[ipoint]);
424  dist[i]+=(y[i]-y[ipoint])*(y[i]-y[ipoint]);
425  dist[i]+=(z[i]-z[ipoint])*(z[i]-z[ipoint]);
426  dist[i]=TMath::Sqrt(dist[i]);
427 
428  }
429  TMath::Sort(npoints, dist, index, kFALSE);
430 
431  point[0]=x[ipoint];
432  point[1]=y[ipoint];
433  point[2]=z[ipoint];
434 
435  kdtree->FindNearestNeighbors(point, nn, index2, dist2);
436 
437 
438  for (Int_t inn=0; inn<nn; inn++){
439  if (TMath::Abs(dist2[inn]-dist[index[inn]])>1E-8) {
440  diff1++;
441  // printf("dist1=%f, dist2=%f, in1=%lld, in2=%d\n", dist[index[inn]], dist2[inn], index[inn], index2[inn]);
442  }
443 
444 
445  }
446  }
447 
448  printf("Nearest neighbors found for %d random points\n", ntimes);
449  printf("%d neighbors are wrong compared to \"brute force\" method\n", diff1);
450 // printf("Old: %d neighbors are wrong compared to brute-force method\n", diff2);
451 
452 // printf("\n");
453 // for (Int_t i=0; i<nn; i++){
454 // printf("ind[%d]=%d, dist[%d]=%f\n", i, index2[i], i, dist2[i]);
455 // }
456 
457 
458 
459 
460  delete [] x;
461  delete [] y;
462  delete [] z;
463  delete [] index;
464  delete [] dist;
465  delete [] index2;
466  delete [] dist2;
467 }
468 
469 ////////////////////////////////////////////////////////////////////////////////
470 
471 void TestRange()
472 {
473 //Test TKDTree::FindInRange() function
474 
475  Int_t npoints = Int_t(gRandom->Uniform(0, 100000));
476  Double_t range = gRandom->Uniform(20, 100);
477 
478  printf("%d points, range=%f\n", npoints, range);
479  Int_t ntimes = 10;
480  Double_t *x = new Double_t[npoints];
481  Double_t *y = new Double_t[npoints];
482  Double_t *z = new Double_t[npoints];
483  for (Int_t i=0; i<npoints; i++){
484  x[i] = gRandom->Uniform(-100, 100);
485  y[i] = gRandom->Uniform(-100, 100);
486  z[i] = gRandom->Uniform(-100, 100);
487  }
488 
489  Int_t *results1 = new Int_t[npoints];
490  std::vector<Int_t> results2;
491  Int_t np1;
492 
493 //Compute with the kd-tree
494  Int_t bsize = 10;
495  TKDTreeID *kdtree = new TKDTreeID(npoints, 3, bsize);
496  kdtree->SetData(0, x);
497  kdtree->SetData(1, y);
498  kdtree->SetData(2, z);
499  kdtree->Build();
500  Double_t *dist = new Double_t[npoints];
501  Int_t *index = new Int_t[npoints];
502  Int_t ndiff = 0;
503  for (Int_t itime=0; itime<ntimes; itime++){
504  Double_t point[3];
505  point[0]=gRandom->Uniform(-90, 90);
506  point[1]=gRandom->Uniform(-90, 90);
507  point[2]=gRandom->Uniform(-90, 90);
508 
509  //printf("point: (%f, %f, %f)\n\n", point[0], point[1], point[2]);
510  for (Int_t ipoint=0; ipoint<npoints; ipoint++){
511  dist[ipoint]=0;
512  dist[ipoint]+=(x[ipoint]-point[0])*(x[ipoint]-point[0]);
513  dist[ipoint]+=(y[ipoint]-point[1])*(y[ipoint]-point[1]);
514  dist[ipoint]+=(z[ipoint]-point[2])*(z[ipoint]-point[2]);
515  dist[ipoint]=TMath::Sqrt(dist[ipoint]);
516  index[ipoint]=ipoint;
517  }
518  TMath::Sort(npoints, dist, index, kFALSE);
519  np1=0;
520  while (np1<npoints && dist[index[np1]]<=range){
521  results1[np1]=index[np1];
522  np1++;
523  }
524  results2.clear();
525  kdtree->FindInRange(point, range, results2);
526 
527  if (TMath::Abs(np1 - Int_t(results2.size()))>0.1) {
528  ndiff++;
529  printf("different numbers of points found, %d %d\n", np1, Int_t(results2.size()));
530  continue;
531  }
532 
533  //have to sort the results, as they are in different order
534  TMath::Sort(np1, results1, index, kFALSE);
535  std::sort(results2.begin(), results2.end());
536 
537  for (Int_t i=0; i<np1; i++){
538  if (TMath::Abs(results1[index[i]]-results2[i])>1E-8) ndiff++;
539  }
540  }
541  printf("%d differences found between \"brute force\" method and kd-tree\n", ndiff);
542 
543  delete [] x;
544  delete [] y;
545  delete [] z;
546  delete [] index;
547  delete [] dist;
548  delete [] results1;
549  delete kdtree;
550 }
551 
552 
553 
554 
555 ////////////////////////////////////////////////////////////////////////////////
556 
557 int main(int argc, char **argv) {
558  // Parse command line arguments
559  for (Int_t i=1 ; i<argc ; i++) {
560  std::string arg = argv[i] ;
561  if (arg == "-g") {
562  showGraphics = true;
563  }
564  // if (arg == "-v") {
565  // showGraphics = true;
566  // verbose = true;
567  // }
568  if (arg == "-h") {
569  std::cerr << "Usage: " << argv[0] << " [-g] [-v]\n";
570  std::cerr << " where:\n";
571  std::cerr << " -g : graphics mode\n";
572  //std::cerr << " -v : verbose mode";
573  std::cerr << std::endl;
574  return -1;
575  }
576  }
577 
578  TApplication* theApp = 0;
579  if ( showGraphics )
580  theApp = new TApplication("App",&argc,argv);
581 
582  kDTreeTest();
583 
584  if ( showGraphics )
585  {
586  theApp->Run();
587  delete theApp;
588  theApp = 0;
589  }
590 
591  return 0;
592 }
double dist(Rotation3D const &r1, Rotation3D const &r2)
Definition: 3DDistances.cxx:48
Int_t GetNNodes() const
Definition: TKDTree.h:35
void TestSpeed(Int_t npower2=20, Int_t bsize=10)
Test of building time of kdTree.
Definition: kDTreeTest.cxx:226
void SetData(Index npoints, Index ndim, UInt_t bsize, Value **data)
Set the data array. See the constructor function comments for details.
Definition: TKDTree.cxx:925
void Start(Bool_t reset=kTRUE)
Start the stopwatch.
Definition: TStopwatch.cxx:56
void TestMembers()
This is not really a test, it's a function that illustrates the internal behaviour of the kd-tree...
Definition: kDTreeTest.cxx:89
Int_t GetRowT0()
Definition: TKDTree.h:46
TKDTree< Int_t, Float_t > TKDTreeIF
Definition: TKDTree.h:107
float Float_t
Definition: RtypesCore.h:53
Float_t Mem()
Definition: kDTreeTest.cxx:35
virtual Double_t Rndm(Int_t i=0)
Machine independent random number generator.
Definition: TRandom.cxx:512
void TestRange()
Definition: kDTreeTest.cxx:471
Value GetNodeValue(Int_t id) const
Definition: TKDTree.h:34
Int_t GetOffset()
cross node
Definition: TKDTree.h:48
Double_t CpuTime()
Stop the stopwatch (if it is running) and return the cputime (in seconds) passed between the start an...
Definition: TStopwatch.cxx:123
void FindInRange(Value *point, Value range, std::vector< Index > &res)
Find all points in the sphere of a given radius "range" around the given point 1st argument - the poi...
Definition: TKDTree.cxx:756
int Int_t
Definition: RtypesCore.h:41
const Bool_t kFALSE
Definition: Rtypes.h:92
void kDTreeTest()
Definition: kDTreeTest.cxx:48
void TestConstr(const Int_t npoints=1000000, const Int_t bsize=100)
compare the results of different data setting functions nothing printed - all works correctly ...
Definition: kDTreeTest.cxx:183
Int_t GetCrossNode()
smallest terminal row
Definition: TKDTree.h:47
Short_t Abs(Short_t d)
Definition: TMathBase.h:110
virtual void Draw(Option_t *chopt="")
Draw this graph with its current attributes.
Definition: TGraph.cxx:740
virtual int GetProcInfo(ProcInfo_t *info) const
Returns cpu and memory used by this process into the ProcInfo_t structure.
Definition: TSystem.cxx:2391
void Build()
Build the kd-tree.
Definition: TKDTree.cxx:413
TStopwatch timer
Definition: pirndm.C:37
void Stop()
Stop the stopwatch.
Definition: TStopwatch.cxx:75
Double_t x[n]
Definition: legend1.C:17
Int_t bsize[]
Definition: SparseFit4.cxx:31
virtual void Run(Bool_t retrn=kFALSE)
Main application eventloop. Calls system dependent eventloop via gSystem.
void TestBuild(const Int_t npoints=1000000, const Int_t bsize=100)
Test kdTree for memory leaks.
Definition: kDTreeTest.cxx:61
double pow(double, double)
void Sort(Index n, const Element *a, Index *index, Bool_t down=kTRUE)
Definition: TMath.h:1002
bool showGraphics
Definition: kDTreeTest.cxx:23
Float_t z[5]
Definition: Ifit.C:16
a kd-tree
Definition: TKDTree.h:11
void TestNeighbors()
Test TKDTree::FindNearestNeighbors() function.
Definition: kDTreeTest.cxx:384
R__EXTERN TSystem * gSystem
Definition: TSystem.h:545
Long_t fMemVirtual
Definition: TSystem.h:207
Double_t E()
Definition: TMath.h:54
void FindNearestNeighbors(const Value *point, Int_t k, Index *ind, Value *dist)
Find kNN nearest neighbors to the point in the first argument Returns 1 on success, 0 on failure Arrays ind and dist are provided by the user and are assumed to be at least kNN elements long.
Definition: TKDTree.cxx:550
virtual void SetMarkerStyle(Style_t mstyle=1)
Definition: TAttMarker.h:53
R__EXTERN TRandom * gRandom
Definition: TRandom.h:62
TKDTree< Int_t, Double_t > TKDTreeID
Definition: TKDTree.h:106
double Double_t
Definition: RtypesCore.h:55
ClassImp(TMCParticle) void TMCParticle printf(": p=(%7.3f,%7.3f,%9.3f) ;", fPx, fPy, fPz)
Double_t y[n]
Definition: legend1.C:17
virtual Double_t Uniform(Double_t x1=1)
Returns a uniform deviate on the interval (0, x1).
Definition: TRandom.cxx:606
virtual void SetPoint(Int_t i, Double_t x, Double_t y)
Set x and y values for point number i.
Definition: TGraph.cxx:2127
A Graph is a graphics object made of two arrays X and Y with npoints each.
Definition: TGraph.h:53
#define gPad
Definition: TVirtualPad.h:288
This class creates the ROOT Application Environment that interfaces to the windowing system eventloop...
Definition: TApplication.h:45
Double_t Sqrt(Double_t x)
Definition: TMath.h:464
int main(int argc, char **argv)
Definition: kDTreeTest.cxx:557
const Bool_t kTRUE
Definition: Rtypes.h:91
Stopwatch class.
Definition: TStopwatch.h:30