#include <guma_rkdtree.h>
Inheritance diagram for guma::kdtsearch::
Public Methods | |
kdtsearch (int dim, int maxNeighbors) | |
void | scan_records (const U &P, const gul::List< gul::ListNode< kdrec< U, V > > > &recs) |
void | process_node (const U &P, const kdtnode< U, V > *n, const gul::Ptr< V > &D, V d, gul::List< gul::ListNode< kdtsnode< U, V > > > &stack) |
V | length (const gul::Ptr< V > &P) |
Static Public Methods | |
int | compare_key_to_node (V *k, kdnnrec< U, V > *r) |
Public Attributes | |
int | m_dim |
int | m_nNeighbors |
V | m_maxDist |
gul::Map< kdnnrec< U, V > > | m_neighbors |
int | m_maxNeighbors |
|
Definition at line 206 of file guma_rkdtree.h. References m_dim, m_maxNeighbors, and m_nNeighbors.
00207 { 00208 m_dim = dim; 00209 m_nNeighbors = 0; 00210 m_maxNeighbors = maxNeighbors; 00211 } |
|
Definition at line 152 of file guma_rkdtree.cpp. Referenced by scan_records().
00153 { 00154 return rtr<V>::cmp( *k, r->m_dist ); 00155 } |
|
Definition at line 158 of file guma_rkdtree.cpp. References m_dim. Referenced by process_node().
00159 { 00160 V dist; 00161 int i; 00162 00163 dist = (V)0; 00164 for( i = 0; i < m_dim; i++ ) 00165 dist += P[i] * P[i]; 00166 dist = rtr<V>::sqrt(dist); 00167 return dist; 00168 } |
|
Definition at line 248 of file guma_rkdtree.cpp. References length(), m_dim, m_maxDist, m_maxNeighbors, m_nNeighbors, and scan_records().
00251 { 00252 int i,j; 00253 V dist,d1,d2; 00254 Ptr<V> D1,D2; 00255 const kdtnode<U,V> *T1, *T2; 00256 ListNode< kdtsnode<U,V> > *sn; 00257 00258 scan_records( P, n->m_recs ); 00259 00260 i = n->m_disc; 00261 dist = P[i] - n->key(); 00262 00263 if( dist < (V)0 ) 00264 { 00265 T1 = n->m_left; 00266 if( T1 ) 00267 { 00268 if( (D[i] > (V)0) || (D[i] < dist) ) // set D1[i] = 0 00269 { 00270 D1.reserve_pool(m_dim); 00271 for( j = 0; j < m_dim; j++ ) 00272 D1[j] = D[j]; 00273 D1[i] = (V)0; 00274 d1 = length( D1 ); 00275 } 00276 else 00277 { 00278 D1 = D; // distance to cell remains the same 00279 d1 = d; 00280 } 00281 } 00282 T2 = n->m_right; 00283 } 00284 else if( dist > 0 ) 00285 { 00286 T1 = n->m_right; 00287 if( T1 ) 00288 { 00289 if( (D[i] < (V)0) || (D[i] > dist) ) // set D1[i] = 0 00290 { 00291 D1.reserve_pool(m_dim); 00292 for( j = 0; j < m_dim; j++ ) 00293 D1[j] = D[j]; 00294 D1[i] = (V)0; 00295 d1 = length( D1 ); 00296 } 00297 else 00298 { 00299 D1 = D; // distance to cell remains the same 00300 d1 = d; 00301 } 00302 } 00303 T2 = n->m_left; 00304 } 00305 else /* dist = 0 */ 00306 { 00307 T1 = n->m_left; 00308 if( T1 ) 00309 { 00310 if( D[i] ) // set D1[i] = 0 00311 { 00312 D1.reserve_pool(m_dim); 00313 for( j = 0; j < m_dim; j++ ) 00314 D1[j] = D[j]; 00315 D1[i] = (V)0; 00316 d1 = length( D1 ); 00317 } 00318 else 00319 { 00320 D1 = D; // distance to cell hasn't changed 00321 d1 = d; 00322 } 00323 } 00324 T2 = n->m_right; 00325 } 00326 00327 if( T2 ) 00328 { 00329 if( dist != D[i] ) // set D2[i] = dist 00330 { 00331 D2.reserve_pool(m_dim); 00332 for( j = 0; j < m_dim; j++ ) 00333 D2[j] = D[j]; 00334 D2[i] = dist; 00335 d2 = length( D2 ); 00336 } 00337 else 00338 { 00339 D2 = D; // distance to cell hasn't changed 00340 d2 = d; 00341 } 00342 } 00343 00344 if( T1 && ((d1 <= m_maxDist) || (m_nNeighbors < m_maxNeighbors)) ) 00345 { 00346 sn = new ListNode< kdtsnode<U,V> >( kdtsnode<U,V>(T1,D1,d1) ); 00347 stack.Append(sn); 00348 } 00349 if( T2 && ((d2 <= m_maxDist) || (m_nNeighbors < m_maxNeighbors)) ) 00350 { 00351 sn = new ListNode< kdtsnode<U,V> >( kdtsnode<U,V>(T2,D2,d2) ); 00352 stack.Append(sn); 00353 } 00354 } |
|
Definition at line 171 of file guma_rkdtree.cpp. References compare_key_to_node(), gul::Map< kdnnrec< U, V > >::FreeNode(), gul::Map< kdnnrec< U, V > >::InsertNode(), gul::Map< kdnnrec< U, V > >::Last(), m_dim, m_maxDist, m_maxNeighbors, m_neighbors, m_nNeighbors, gul::Map< kdnnrec< U, V > >::NewNode(), gul::Map< kdnnrec< U, V > >::Predecessor(), gul::Map< kdnnrec< U, V > >::RemoveNode(), gul::Map< kdnnrec< U, V > >::root, and gul::Map< kdnnrec< U, V > >::SearchNode(). Referenced by process_node().
00173 { 00174 ListNode< kdrec<U,V> > *rec; 00175 V dist,d; 00176 int i,side; 00177 Map< kdnnrec<U,V> >::Node mnode,mnode1; 00178 00179 for( rec = recs.First(); rec; rec = rec->next ) 00180 { 00181 dist = (V)0; 00182 for( i = 0; i < m_dim; i++ ) 00183 { 00184 d = P[i] - rec->el[i]; 00185 dist += d * d; 00186 } 00187 dist = rtr<V>::sqrt(dist); 00188 00189 if( m_nNeighbors == 0 ) // initialize 00190 { 00191 m_maxDist = dist; 00192 00193 // 00194 // the following two lines are a replacement for 00195 // 00196 // "mnode = m_neighbors.NewNode(nnrec(dist,rec->el));" 00197 // 00198 // which doesn't works with gcc 3.0 anymore (???): 00199 // 00200 mnode = m_neighbors.NewNode(); 00201 mnode.key()->m_dist = dist; 00202 mnode.key()->m_recs.Append( new gul::ListNode< kdrec<U,V> >(rec->el) ); 00203 00204 m_neighbors.InsertNode( mnode, m_neighbors.root, 1 ); 00205 00206 m_nNeighbors++; 00207 00208 continue; 00209 } 00210 00211 if( (m_nNeighbors == m_maxNeighbors) && (dist > m_maxDist) ) // too far away 00212 continue; 00213 00214 side = m_neighbors.SearchNode( &dist, compare_key_to_node, &mnode); 00215 if( side == 0 ) // there is already a node with the same distancce 00216 { 00217 mnode.key()->m_recs.Append( new ListNode< kdrec<U,V> >(rec->el) ); 00218 } 00219 else // insert a new node 00220 { 00221 if( dist > m_maxDist ) 00222 m_maxDist = dist; 00223 00224 mnode1 = m_neighbors.NewNode(); 00225 mnode1.key()->m_dist = dist; 00226 mnode1.key()->m_recs.Append( new gul::ListNode< kdrec<U,V> >(rec->el) ); 00227 00228 m_neighbors.InsertNode( mnode1, mnode, side ); 00229 m_nNeighbors++; 00230 } 00231 00232 if( m_nNeighbors > m_maxNeighbors ) // remove the last node 00233 { 00234 mnode = m_neighbors.Last(); 00235 00236 mnode1 = m_neighbors.Predecessor(mnode); 00237 m_maxDist = mnode1.key()->m_dist; 00238 00239 m_neighbors.RemoveNode(mnode); 00240 m_neighbors.FreeNode(mnode); 00241 00242 m_nNeighbors--; 00243 } 00244 } 00245 }; |
|
Definition at line 199 of file guma_rkdtree.h. Referenced by kdtsearch(), length(), process_node(), and scan_records(). |
|
Definition at line 201 of file guma_rkdtree.h. Referenced by process_node(), and scan_records(). |
|
Definition at line 203 of file guma_rkdtree.h. Referenced by kdtsearch(), process_node(), and scan_records(). |
|
Definition at line 202 of file guma_rkdtree.h. Referenced by scan_records(). |
|
Definition at line 200 of file guma_rkdtree.h. Referenced by kdtsearch(), process_node(), and scan_records(). |