cgma
OctTreeCell.cpp
Go to the documentation of this file.
00001 //-------------------------------------------------------------------------
00002 // Filename      : OctTreeCell.cpp
00003 //
00004 // Purpose       : Oct-tree node used by OctTree
00005 //
00006 // Special Notes : OctTree handles all memory allocation for this
00007 //                 class.
00008 //
00009 // Creator       : Jason Kraftcheck
00010 //
00011 // Creation Date : 01/30/02
00012 //-------------------------------------------------------------------------
00013 
00014 #include "OctTreeCell.hpp"
00015 #include "CubitVector.hpp"
00016 
00017 template <class X, class E>
00018 OctTreeCell<X,E>::OctTreeCell( OctTreeEntry<X,E> array[], int size )
00019   : node_count_(size)
00020 {
00021   children_ = 0;
00022   OctTreeEntry<X,E>** prev_ptr_ptr = &head_;
00023   for( int i = 0; i < node_count_; i++ )
00024   {
00025     OctTreeEntry<X,E>* entry = array + i;
00026     *prev_ptr_ptr = entry;
00027     prev_ptr_ptr = &(entry->next);
00028   }
00029   *prev_ptr_ptr = 0;
00030 }
00031 
00032 template <class X, class E>
00033 void OctTreeCell<X,E>::append_nodes( DLIList<X*>& list )
00034 {
00035   OctTreeEntry<X,E>* entry = node_count_ ? head_ : 0;
00036   for( ; entry; entry = entry->next )
00037     list.append( entry->node );
00038 }
00039   
00040 template <class X, class E>
00041 void OctTreeCell<X,E>::append_all_nodes( DLIList<X*>& list )
00042 {
00043   if( node_count_ )
00044   {
00045     append_nodes( list );
00046   }
00047   else if( children_ )
00048   {
00049     for( int i = 0; i < 8; i++ )
00050       children_[i].append_all_nodes( list );
00051   }
00052 }
00053 
00054 template <class X, class E>
00055 void OctTreeCell<X,E>::add_nodes( OctTreeEntry<X,E>* node )
00056 {
00057   assert( leaf() );
00058   
00059   OctTreeEntry<X,E>* last = node;
00060   int count = 1;
00061   while( last->next ) 
00062   {
00063     count++;
00064     last = last->next;
00065   }
00066   
00067   last->next = head_;
00068   head_ = node;
00069   node_count_ += count;
00070 }
00071 
00072 template <class X, class E>
00073 OctTreeCell<X,E>* OctTreeCell<X,E>::child( int quadrant )
00074 {
00075   assert( quadrant >= 0 && quadrant < 8 && !node_count_ );
00076   if( children_ )
00077     return children_ + quadrant;
00078   else
00079     return 0;
00080 }
00081 
00082 template <class X, class E>
00083 bool OctTreeCell<X,E>::split( const CubitVector& my_center,
00084                             OctTreeCell<X,E>* storage )
00085 {
00086   assert( leaf() );
00087   bool result = false;
00088   
00089   if( node_count_ > 3 ) 
00090   {
00091       // Data is a union.  Make sure you never change
00092       // the order of the following two lines!
00093     OctTreeEntry<X,E>* node = head_;
00094     children_ = storage;
00095 
00096     while( node )
00097     {
00098       CubitVector coords = E::coordinates(node->node);
00099       int x = coords.x() < my_center.x() ? X_MIN : X_MAX;
00100       int y = coords.y() < my_center.y() ? Y_MIN : Y_MAX;
00101       int z = coords.z() < my_center.z() ? Z_MIN : Z_MAX;
00102       OctTreeEntry<X,E>* next = node->next;
00103       node->next = 0;
00104       children_[x|y|z].add_nodes( node );
00105       node = next;
00106     }
00107     result = true;
00108     node_count_ = 0;
00109   }
00110   
00111   return result;
00112 }  
00113   
00114 template <class X, class E>
00115 void OctTreeCell<X,E>::node_locations( CubitVector& box_min,
00116                                      CubitVector& box_max,
00117                                      CubitVector& average,
00118                                      CubitVector* std_dev )
00119 {
00120   if( !node_count_ )
00121     return;
00122 
00123 
00124   double x_min, y_min, z_min;
00125   double x_max, y_max, z_max;
00126   double x_avg, y_avg, z_avg;
00127   CubitVector coords = E::coordinates( head_->node );
00128   x_min = x_max = x_avg = coords.x();
00129   y_min = y_max = y_avg = coords.y();
00130   z_min = z_max = z_avg = coords.z();
00131   
00132   for( OctTreeEntry<X,E>* entry = head_->next; entry; entry = entry->next )
00133   {
00134     X* node = entry->node;
00135     coords = E::coordinates( node );
00136 
00137     double x = coords.x();
00138     if( x < x_min ) x_min = x;
00139     else if ( x > x_max ) x_max = x;
00140     x_avg += x;
00141     
00142     double y = coords.y();
00143     if( y < y_min ) y_min = y;
00144     else if ( y > y_max ) y_max = y;
00145     y_avg += y;
00146     
00147     double z = coords.z();
00148     if( z < z_min ) z_min = z;
00149     else if ( z > z_max ) z_max = z;
00150     z_avg += z;
00151   }
00152   
00153   box_min.set( x_min, y_min, z_min );
00154   box_max.set( x_max, y_max, z_max );
00155   
00156   double inv = 1.0 / node_count_;
00157   x_avg *= inv;
00158   y_avg *= inv;
00159   z_avg *= inv;
00160   average.set( x_avg, y_avg, z_avg );
00161   
00162   if( std_dev )
00163   {
00164     X* hn = head_->node;
00165     coords = E::coordinates(hn);
00166     double x_dev = (coords.x() - x_avg) * (coords.x() - x_avg);
00167     double y_dev = (coords.y() - y_avg) * (coords.y() - y_avg);
00168     double z_dev = (coords.z() - z_avg) * (coords.z() - z_avg);
00169 
00170     for( OctTreeEntry<X,E>* entry = head_->next; entry; entry = entry->next )
00171     {
00172       X* node = entry->node;
00173       coords = E::coordinates(node);
00174 
00175       double x = coords.x();
00176       double dx = x - x_avg;
00177       x_dev += dx * dx;
00178 
00179       double y = coords.y();
00180       double dy = y - y_avg;
00181       y_dev += dy * dy;
00182 
00183       double z = coords.z();
00184       double dz = z - z_avg;
00185       z_dev += dz * dz;
00186     }
00187 
00188     inv = 1.0 / ( node_count_ - 1 );
00189     x_dev = sqrt(x_dev * inv);
00190     y_dev = sqrt(y_dev * inv);
00191     z_dev = sqrt(z_dev * inv);
00192 
00193     std_dev->set( x_dev, y_dev, z_dev );
00194   }
00195 }
00196 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines