---

guma_rkdtree.h

Go to the documentation of this file.

/* LIBGUL - Geometry Utility Library
 * Copyright (C) 1998-1999 Norbert Irmer
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
 
#ifndef GUMA_RKDTREE_H
#define GUMA_RKDTREE_H

namespace guma {

// this struct is used to preserve the identity of points (since different
// points may have the same coordinates
template< class U, class V >
class kdrec : public gul::pool_object
{
public:
  const U *m_base;
  kdrec( const U *base ) { m_base = base; }
  const V& operator[]( size_t i) const { return (*m_base)[i]; } 
};

// object for the nodes of a kd-tree
template< class U, class V >
class kdtnode : public gul::pool_object
{
public:
  int                               m_disc;   // discriminant
  gul::List< gul::ListNode< kdrec<U,V> > > m_recs;
  int                               m_nelems;

  kdtnode     *m_left;   // left subtree
  kdtnode     *m_right;  // right subtree
  kdtnode     *m_parent; // to travel from a node to the root of the tree

  kdtnode( const kdrec<U,V>& rec, int disc )
  {
    m_disc = disc;
    m_recs.Append( new gul::ListNode< kdrec<U,V> >(rec) );
    m_left = m_right = m_parent = 0;
    m_nelems = 1;
  }
  kdtnode( gul::List< gul::ListNode< kdrec<U,V> > >& recs, int disc )
  {
    m_disc = disc;
    m_recs = recs;
    m_left = m_right = m_parent = 0;
    m_nelems = 1;
  }
  const V& key() const
  {
    return m_recs.First()->el[m_disc];
  }
  void add_rec( const kdrec<U,V>& rec )
  {
    m_recs.Append( new gul::ListNode< kdrec<U,V> >(rec) );
  }
  void update()
  {
    m_nelems = 1;
    if( m_left ) m_nelems += m_left->m_nelems;
    if( m_right ) m_nelems += m_right->m_nelems;
    if( m_parent ) m_parent->update();
  }
  void set_left( kdtnode *left )
  {
    m_left = left;
    if( m_left ) m_left->m_parent = this;
    update();
  }
  void set_right( kdtnode *right )
  {
    m_right = right;
    if( m_right ) m_right->m_parent = this;
    update();
  }
  void set_childs( kdtnode *left, kdtnode *right )
  {
    m_left = left;
    if( m_left ) m_left->m_parent = this;
    m_right = right;
    if( m_right ) m_right->m_parent = this;
    update();
  }
  void unlink( kdtnode **left, kdtnode **right, 
               gul::List< gul::ListNode< kdrec<U,V> > >& L)
  {
    L += m_recs;

    *left = m_left;   
    if( m_left ) 
    {
      m_left->m_parent = 0;
      m_left = 0;
    }
    *right = m_right;   
    if( m_right ) 
    {
      m_right->m_parent = 0;
      m_right = 0;
    }
    if( m_parent )
    {
      if( m_parent->m_left == this )
        m_parent->m_left = 0;
      if( m_parent->m_right == this )
        m_parent->m_right = 0;
      m_parent->update();
      m_parent = 0;
    }
  }
  ~kdtnode()
  {
    if( m_left ) 
    {
      m_left->m_parent = 0;
      delete m_left;
    }
    if( m_right ) 
    {
      m_right->m_parent = 0;
      delete m_right;
    }
    if( m_parent )
    {
      if( m_parent->m_left == this )
        m_parent->m_left = 0;
      if( m_parent->m_right == this )
        m_parent->m_right = 0;
      m_parent->update();
    }
  }
  // debugging functions
  void height( int cur_height, int *max_height, 
               int *avg_count, double *avg_sum );
  void dump(int dim,int space);
};

// struct for returning results of nearest neighbor search
template< class U, class V >
class kdnnrec : public gul::pool_object
{
public:
  V                                         m_dist;
  gul::List< gul::ListNode< kdrec<U,V> > >  m_recs; // a list, since duplicate 
                // records or records with the same distance are possible
  kdnnrec() { }
    
  kdnnrec( const V& dist, const kdrec<U,V>& rec )
  {
    m_dist = dist;
    m_recs.Append( new gul::ListNode< kdrec<U,V> >(rec) );
  }
  kdnnrec<U,V>& operator=( kdnnrec<U,V>& other )
  {
    if( this == &other ) return *this;

    m_dist = other.m_dist;
    m_recs = other.m_recs;
    return *this;
  }
  // debugging functions
  GULAPI void dump( int dim );
};

// these objects are used internally while finding nearest neighbors
template< class U, class V >
class kdtsnode : public gul::pool_object
{
public:
  const kdtnode<U,V>  *m_n;
  gul::Ptr<V>          m_D;
  V                    m_d;
  kdtsnode( const kdtnode<U,V> *n, const gul::Ptr<V>& D, V d )
  {
    m_n = n;
    m_D = D;
    m_d = d;
  } 
};

template< class U, class V >
class kdtsearch : public gul::pool_object
{
public:
  int                                   m_dim;
  int                                   m_nNeighbors;
  V                                     m_maxDist;
  gul::Map< kdnnrec<U,V> >              m_neighbors;
  int                                   m_maxNeighbors;

  // important: maxNeighbors must be at least 1 !!!
  kdtsearch( int dim, int maxNeighbors )
  {
    m_dim = dim;
    m_nNeighbors = 0;
    m_maxNeighbors = 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 );
  
  static int compare_key_to_node( V *k, kdnnrec<U,V> *r );
  V length( const gul::Ptr<V>& P );
};


/* ------------------------------------------------------------------------
  class with base functionality (but without a special random number generator)
-------------------------------------------------------------------------*/
template< class U, class V >
class rkdtree_base : public gul::pool_object
{
public:
  int           m_dim;
  kdtnode<U,V> *m_root;

  rkdtree_base( int dim ) { m_dim = dim; m_root = 0; }
  ~rkdtree_base() { delete m_root; }

  // the array M has to be reserved by the caller
  GULAPI int nearest_neighbors(  const U& P, int m, gul::Ptr< kdnnrec<U,V> >& M  );

  void split_recs(  
    gul::List< gul::ListNode< kdrec<U,V> > >& recs, const V& key, int i, 
    gul::List< gul::ListNode< kdrec<U,V> > >& recs1, 
    gul::List< gul::ListNode< kdrec<U,V> > >& recs2,
    gul::List< gul::ListNode< kdrec<U,V> > >& C );
  void split_recs(  
    gul::List< gul::ListNode< kdrec<U,V> > >& recs, const U& X, int i, 
    gul::List< gul::ListNode< kdrec<U,V> > >& recs1,
    gul::List< gul::ListNode< kdrec<U,V> > >& recs2,
    gul::List< gul::ListNode< kdrec<U,V> > >& C )
  {
    split_recs( recs, X[i], i, recs1, recs2, C );
  }

  // debugging functions
  GULAPI void dump_statistics();
  GULAPI void dump_tree();
};

/*--------------------------------------------------------------------------
  randomized kd-tree
--------------------------------------------------------------------------*/
template< class U, class V, class Rand >
class rkdtree : public rkdtree_base<U,V>
{
public:
  rkdtree( int dim ) : rkdtree_base<U,V>(dim) { }
  ~rkdtree() { }

  void insert( const U *rec ) { m_root = insert(m_root, kdrec<U,V>(rec)); }
  void remove( const U *rec, gul::List< gul::ListNode< kdrec<U,V> > >& outrecs ) 
  { 
    m_root = remove(m_root, kdrec<U,V>(rec), outrecs);
  }

  GULAPI kdtnode<U,V> *insert( kdtnode<U,V> *T, const kdrec<U,V>& rec );
  GULAPI kdtnode<U,V> *remove( 
                 kdtnode<U,V> *T, 
                 const kdrec<U,V>& rec,
                 gul::List< gul::ListNode< kdrec<U,V> > >& outrecs );

  void split( kdtnode<U,V> *T, const V& key, int i, 
              kdtnode<U,V> **retL, kdtnode<U,V> **retR, 
              gul::List< gul::ListNode< kdrec<U,V> > >& C );
  void split( kdtnode<U,V> *T, const kdrec<U,V>& X, int i, 
              kdtnode<U,V> **retL, kdtnode<U,V> **retR, 
              gul::List< gul::ListNode< kdrec<U,V> > >& C ) 
  {
    split( T, X[i], i, retL, retR, C );
  }

  kdtnode<U,V> *join( kdtnode<U,V> *A, kdtnode<U,V> *B, int i );
};

}

#endif

---