cgma
KDDTreeNode.cpp
Go to the documentation of this file.
00001 //-----------------------------------------------------------------
00002 //- Class:   KDDTreeNode
00003 //- Author:  Kevin Albrecht 
00004 //- Created: 13 May 2003
00005 //- Updated: 8 Feb 2004
00006 //-
00007 //- Description:
00008 //-   Node for dynamic version of the k-d tree, where k=3.
00009 //-
00010 //- References:
00011 //-
00012 //-   Hanan Samet.  Design and Analysis of Spatial Data Structures.
00013 //-      Addison-Wesley, Reading, MA, 1990.
00014 //-
00015 //-   Jon Louis Bentley. Multidimensional binary search trees used
00016 //-     for associative searching. In Communications of the ACM,
00017 //-     18(9), pages 509-517, September 1975.
00018 //-----------------------------------------------------------------
00019 
00020 //---------------------------------
00021 // Include Files
00022 //---------------------------------
00023 
00024 #include "KDDTreeNode.hpp"
00025 #include "DLIList.hpp"
00026 
00027 //---------------------------
00028 // Initialize Static Members
00029 //---------------------------
00030 
00031 #ifdef INLINE_TEMPLATES
00032   #define MY_INLINE inline
00033 #else
00034   #define MY_INLINE
00035 #endif
00036 
00037 //- Constructor
00038 template <class Y> MY_INLINE KDDTreeNode<Y>::KDDTreeNode
00039   ( Y aData, DIMENSION aDisc )
00040 {
00041   parent = left = right = NULL;
00042   data = aData;
00043 
00044   boundingBox = data->bounding_box();
00045   x = boundingBox.center().x();
00046   y = boundingBox.center().y();
00047   z = boundingBox.center().z();
00048 
00049   myDist = CUBIT_DBL_MAX;
00050   myDistData = DD_SAFETY;
00051    
00052   myDisc = aDisc;
00053 
00054   valid = CUBIT_TRUE;
00055 }
00056 
00057 //- Destructor
00058 template <class Y> MY_INLINE KDDTreeNode<Y>::~KDDTreeNode ()
00059 {  
00060 }
00061 
00062 template <class Y> MY_INLINE KDDTreeNode<Y> *KDDTreeNode<Y>::get_child (DIRECTION dir) const
00063 {
00064   if (dir == DIR_LEFT) return left;
00065   return right;
00066 }
00067 
00068 template <class Y> MY_INLINE void KDDTreeNode<Y>::set_child
00069   ( KDDTreeNode<Y> *node,
00070     DIRECTION dir )
00071 {
00072   if (dir == DIR_LEFT)
00073   {
00074     left = node;
00075   }
00076   else
00077   {
00078     right = node;
00079   }
00080 }
00081 
00082 template <class Y> MY_INLINE DIMENSION KDDTreeNode<Y>::next_disc () const
00083 {
00084   switch (myDisc)
00085   {
00086     case DIMX: return DIMY;
00087     case DIMY: return DIMZ;
00088     default:   return DIMX;
00089   }
00090 }
00091 
00092 //- The KD_COMPARE function as defined by Samet
00093 template <class Y> MY_INLINE DIRECTION KDDTreeNode<Y>::compare (KDDTreeNode<Y> *Q) const
00094 {
00095   if (Q->myDisc == DIMX)
00096   {
00097     if (x <= Q->x) return DIR_LEFT;
00098     else return DIR_RIGHT;
00099   }
00100   else if (Q->myDisc == DIMY)
00101   {
00102     if (y <= Q->y) return DIR_LEFT;
00103     else return DIR_RIGHT;
00104   }
00105   else if (z <= Q->z)
00106   {
00107     return DIR_LEFT;
00108   }
00109   else
00110   {
00111     return DIR_RIGHT;
00112   }
00113 }
00114 
00115 //- The KD_COMPARE function as defined by Samet
00116 template <class Y> MY_INLINE DIRECTION KDDTreeNode<Y>::compare_with_equality (KDDTreeNode<Y> *Q) const
00117 {
00118   if (Q->myDisc == DIMX)
00119   {
00120     if (x < Q->x) return DIR_LEFT;
00121     else if (x == Q->x) return DIR_EITHER;
00122     else return DIR_RIGHT;
00123   }
00124   else if (Q->myDisc == DIMY)
00125   {
00126     if (y < Q->y) return DIR_LEFT;
00127     else if (y == Q->y) return DIR_EITHER;
00128     else return DIR_RIGHT;
00129   }
00130   else if (z < Q->z)
00131   {
00132     return DIR_LEFT;
00133   }
00134   else if (z == Q->z)
00135   {
00136     return DIR_EITHER;
00137   }
00138   else
00139   {
00140     return DIR_RIGHT;
00141   }
00142 }
00143 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines