#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(). |
1.2.13.1 written by Dimitri van Heesch,
© 1997-2001