Subversion Repositories gelsvn

Rev

Rev 67 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
65 jab 1 
/**
2 
	 Small test program for KDTree class. The idea is to insert a lot of points
3 
	 and find them again. Next a range search is used to test the find point
4 
	 inside sphere function.
5 
 
6 
	 Send bug reports or improvements to jab@imm.dtu.dk
7 
*/
8 
 
9 
#include <cstdlib>
10 
#include "Geometry/KDTree.h"
11 
#include "CGLA/Vec3f.h"
12 
 
13 
using namespace GEO;
14 
using namespace std;
15 
using namespace CGLA;
16 
 
17 
void make_ran_point(Vec3f& p0)
18 
{
72 bj 19 
	p0=Vec3f(10.0f*rand()/RAND_MAX,
20 
					 10.0f*rand()/RAND_MAX,
21 
					 10.0f*rand()/RAND_MAX);
65 jab 22 
}
23 
 
24 
int main()
25 
{
26 
	cout << "\n\nTest 1: Insert and find " << endl;
27 
	int sizes[15] = {1,2,3,4,7,21,134,256,589,678,751,892,1023,1024,1025};
28 
	for(int i=0;i<15;++i)
29 
		{
30 
			int N=sizes[i];
31 
			cout << "Tree size " << N << endl;
72 bj 32 
			srand(0);
65 jab 33 
			cout << "Insert and find points " << endl;
34 
			KDTree<Vec3f,int> tree;
35 
			for(int i=0;i<N;++i)
36 
				{
37 
					Vec3f p0;
38 
					make_ran_point(p0);
39 
					tree.insert(p0, i);
40 
				}
41 
			tree.build();
72 bj 42 
			srand(0);
65 jab 43 
			for(int i=0;i<N;++i)
44 
				{
45 
					Vec3f p0;
46 
					make_ran_point(p0);
47 
					Vec3f pos;
48 
					float d = 0.0000001;
49 
					int x;
50 
					if(!tree.closest_point(p0, d, pos, x))
51 
						{
52 
							cout << " test failed " << endl;
53 
							exit(1);
54 
						}
55 
					assert(x==i);
56 
				}
57 
		}
58 
 
59 
	cout << "Test passed " << endl;
60 
 
61 
	cout << "\n\nTest 2: Points in range " << endl;
62 
	KDTree<Vec3f,int> tree;
63 
	int K = 312;
64 
	for(int i=0;i<K;++i)
65 
		{
66 
			Vec3f p0;
67 
			make_ran_point(p0);
68 
			tree.insert(p0, i);
69 
		}
70 
 
71 
	cout << "Building tree of size = " << K <<endl;
72 
	tree.build();
73 
 
74 
	Vec3f p0;
75 
	make_ran_point(p0);
76 
	std::vector<Vec3f> keys;
77 
	std::vector<int> vals;
78 
 
79 
	float range = 1.95;
80 
	int N = tree.in_sphere(p0, range , keys, vals);
81 
 
82 
	cout << "Points in range (" << range << "): " << N << endl;
83 
	for(int i=0;i<N;++i)
84 
		{
85 
			cout << keys[i] << (keys[i]-p0).length() << " - " << vals[i] << endl;
86 
		}
87 
}