Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

guma::kdtsearch Class Template Reference

#include <guma_rkdtree.h>

Inheritance diagram for guma::kdtsearch::

gul::pool_object List of all members.

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)
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
m_maxDist
gul::Map< kdnnrec< U, V > > m_neighbors
int m_maxNeighbors

template<class U, class V>
class guma::kdtsearch< U, V >


Constructor & Destructor Documentation

template<class U, class V>
guma::kdtsearch< U, V >::kdtsearch int    dim,
int    maxNeighbors
[inline]
 

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   }


Member Function Documentation

template<class U, class V>
int guma::kdtsearch< U, V >::compare_key_to_node V *    k,
kdnnrec< U, V > *    r
[static]
 

Definition at line 152 of file guma_rkdtree.cpp.

Referenced by scan_records().

00153 {
00154   return rtr<V>::cmp( *k, r->m_dist ); 
00155 } 

template<class U, class V>
V guma::kdtsearch< U, V >::length const gul::Ptr< V > &    P
 

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 }

template<class U, class V>
void guma::kdtsearch< U, V >::process_node const U &    P,
const kdtnode< U, V > *    n,
const gul::Ptr< V > &    D,
  d,
gul::List< gul::ListNode< kdtsnode< U, V > > > &    stack
 

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 }

template<class U, class V>
void guma::kdtsearch< U, V >::scan_records const U &    P,
const gul::List< gul::ListNode< kdrec< U, V > > > &    recs
 

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 };


Member Data Documentation

template<class U, class V>
int guma::kdtsearch::m_dim
 

Definition at line 199 of file guma_rkdtree.h.

Referenced by kdtsearch(), length(), process_node(), and scan_records().

template<class U, class V>
V guma::kdtsearch::m_maxDist
 

Definition at line 201 of file guma_rkdtree.h.

Referenced by process_node(), and scan_records().

template<class U, class V>
int guma::kdtsearch::m_maxNeighbors
 

Definition at line 203 of file guma_rkdtree.h.

Referenced by kdtsearch(), process_node(), and scan_records().

template<class U, class V>
gul::Map< kdnnrec<U,V> > guma::kdtsearch::m_neighbors
 

Definition at line 202 of file guma_rkdtree.h.

Referenced by scan_records().

template<class U, class V>
int guma::kdtsearch::m_nNeighbors
 

Definition at line 200 of file guma_rkdtree.h.

Referenced by kdtsearch(), process_node(), and scan_records().


The documentation for this class was generated from the following files:
Generated on Mon Jan 21 04:18:03 2002 for GUL 0.6 - Geometry Utility Library by doxygen1.2.13.1 written by Dimitri van Heesch, © 1997-2001