Subversion Repositories gelsvn

Rev

Rev 203 | Rev 330 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 203 Rev 324
Line 54... Line 54...
54 
		bool is_built;
 54 
		bool is_built;
55 
 
 55 
 
56 
		/// The greatest depth of KD tree.
 56 
		/// The greatest depth of KD tree.
57 
		int max_depth;
 57 
		int max_depth;
58 
 
 58 
 
- 
 
 59 
		/// The dimension -- K
- 
 
 60 
		const int DIM;
- 
 
 61 
 
59 
		/// Total number of elements in tree
 62 
		/// Total number of elements in tree
60 
		int elements;
 63 
		int elements;
61 
 
 64 
 
62 
		/** Comp is a class used for comparing two keys. Comp is constructed
 65 
		/** Comp is a class used for comparing two keys. Comp is constructed
63 
				with the discriminator - i.e. the coordinate of the key that is used
 66 
				with the discriminator - i.e. the coordinate of the key that is used
Line 85... Line 88...
85 
			{
 88 
			{
86 
				return (*this)(k0.key,k1.key);
 89 
				return (*this)(k0.key,k1.key);
87 
			}
 90 
			}
88 
		};
 91 
		};
89 
 
 92 
 
90 
		/// The dimension -- K
 - 
 
91 
		const int DIM;
 - 
 
92 
 
 93 
 
93 
		/** Passed a vector of keys, this function will construct an optimal tree.
 94 
		/** Passed a vector of keys, this function will construct an optimal tree.
94 
				It is called recursively - second argument is level in tree. */
 95 
				It is called recursively - second argument is level in tree. */
95 
		void optimize(int, int, int, int);
 96 
		void optimize(int, int, int, int);
96 
 
 97 
 
Line 141... Line 142...
141 
 
 142 
 
142 
		/** Find the key value pair closest to the key given as first
143 
		/** Find the key value pair closest to the key given as first
143 
				argument. The second argument is the maximum search distance.
 144 
				argument. The second argument is the maximum search distance.
144 
				The final two arguments contain the closest key and its
145 
				The final two arguments contain the closest key and its
145 
				associated value upon return. */
 146 
				associated value upon return. */
146 
		bool closest_point(const KeyT& p, float& dist, KeyT&k, ValT&v) const
 147 
		bool closest_point(const KeyT& p, ScalarType& dist, KeyT&k, ValT&v) const
147 
		{
 148 
		{
148 
			assert(is_built);
 149 
			assert(is_built);
149 
			float max_sq_dist = CGLA::sqr(dist);
 150 
			ScalarType max_sq_dist = CGLA::sqr(dist);
150 
			if(int n = closest_point_priv(1, p, max_sq_dist))
 151 
			if(int n = closest_point_priv(1, p, max_sq_dist))
151 
				{
 152 
				{
152 
					k = nodes[n].key;
 153 
					k = nodes[n].key;
153 
					v = nodes[n].val;
 154 
					v = nodes[n].val;
154 
					dist = std::sqrt(max_sq_dist);
 155 
					dist = std::sqrt(max_sq_dist);
Line 159... Line 160...
159 
 
 160 
 
160 
		/** Find all the elements within a given radius (second argument) of
 161 
		/** Find all the elements within a given radius (second argument) of
161 
				the key (first argument). The key value pairs inside the sphere are
 162 
				the key (first argument). The key value pairs inside the sphere are
162 
				returned in a pair of vectors passed as the two last arguments. */
 163 
				returned in a pair of vectors passed as the two last arguments. */
163 
		int in_sphere(const KeyType& p,
164 
		int in_sphere(const KeyType& p,
164 
									float dist,
 165 
									ScalarType dist,
165 
									std::vector<KeyT>& keys,
 166 
									std::vector<KeyT>& keys,
166 
									std::vector<ValT>& vals) const
 167 
									std::vector<ValT>& vals) const
167 
		{
 168 
		{
168 
			assert(is_built);
 169 
			assert(is_built);
169 
			float max_sq_dist = CGLA::sqr(dist);
 170 
			ScalarType max_sq_dist = CGLA::sqr(dist);
170 
			in_sphere_priv(1,p,max_sq_dist,keys,vals);
 171 
			in_sphere_priv(1,p,max_sq_dist,keys,vals);
171 
			return keys.size();
 172 
			return keys.size();
172 
		}
 173 
		}
173
174
174 
 
 175 
 
Line 266... Line 267...
266 
				ret_node = n;
 267 
				ret_node = n;
267 
			}
 268 
			}
268 
		if(nodes[n].dsc != -1)
 269 
		if(nodes[n].dsc != -1)
269 
			{
 270 
			{
270 
				int dsc         = nodes[n].dsc;
 271 
				int dsc         = nodes[n].dsc;
271 
				float dsc_dist  = CGLA::sqr(nodes[n].key[dsc]-p[dsc]);
 272 
				ScalarType dsc_dist  = CGLA::sqr(nodes[n].key[dsc]-p[dsc]);
272 
				bool left_son   = Comp(dsc)(p,nodes[n].key);
 273 
				bool left_son   = Comp(dsc)(p,nodes[n].key);
273 
 
 274 
 
274 
				if(left_son||dsc_dist<dist)
 275 
				if(left_son||dsc_dist<dist)
275 
					{
 276 
					{
276 
						int left_child = 2*n;
 277 
						int left_child = 2*n;
Line 304... Line 305...
304 
				vals.push_back(nodes[n].val);
 305 
				vals.push_back(nodes[n].val);
305 
			}
 306 
			}
306 
		if(nodes[n].dsc != -1)
 307 
		if(nodes[n].dsc != -1)
307 
			{
 308 
			{
308 
				const int dsc         = nodes[n].dsc;
 309 
				const int dsc         = nodes[n].dsc;
309 
				const float dsc_dist  = CGLA::sqr(nodes[n].key[dsc]-p[dsc]);
 310 
				const ScalarType dsc_dist  = CGLA::sqr(nodes[n].key[dsc]-p[dsc]);
310 
 
 311 
 
311 
				bool left_son = Comp(dsc)(p,nodes[n].key);
 312 
				bool left_son = Comp(dsc)(p,nodes[n].key);
312 
 
 313 
 
313 
				if(left_son||dsc_dist<dist)
 314 
				if(left_son||dsc_dist<dist)
314 
					{
 315 
					{