1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//-----------------------------------------------------------------
//- Class:   KDDTreeNode
//- Author:  Kevin Albrecht 
//- Created: 13 May 2003
//- Updated: 8 Feb 2004
//-
//- Description:
//-   Node for dynamic version of the k-d tree, where k=3.
//-
//- References:
//-
//-   Hanan Samet.  Design and Analysis of Spatial Data Structures.
//-      Addison-Wesley, Reading, MA, 1990.
//-
//-   Jon Louis Bentley. Multidimensional binary search trees used
//-     for associative searching. In Communications of the ACM,
//-     18(9), pages 509-517, September 1975.
//-----------------------------------------------------------------

//---------------------------------
// Include Files
//---------------------------------

#include "KDDTreeNode.hpp"
#include "DLIList.hpp"

//---------------------------
// Initialize Static Members
//---------------------------

#ifdef INLINE_TEMPLATES
  #define MY_INLINE inline
#else
  #define MY_INLINE
#endif

//- Constructor
template <class Y> MY_INLINE KDDTreeNode<Y>::KDDTreeNode
  ( Y aData, DIMENSION aDisc )
{
  parent = left = right = NULL;
  data = aData;

  boundingBox = data->bounding_box();
  x = boundingBox.center().x();
  y = boundingBox.center().y();
  z = boundingBox.center().z();

  myDist = CUBIT_DBL_MAX;
  myDistData = DD_SAFETY;
   
  myDisc = aDisc;

  valid = CUBIT_TRUE;
}

//- Destructor
template <class Y> MY_INLINE KDDTreeNode<Y>::~KDDTreeNode ()
{  
}

template <class Y> MY_INLINE KDDTreeNode<Y> *KDDTreeNode<Y>::get_child (DIRECTION dir) const
{
  if (dir == DIR_LEFT) return left;
  return right;
}

template <class Y> MY_INLINE void KDDTreeNode<Y>::set_child
  ( KDDTreeNode<Y> *node,
    DIRECTION dir )
{
  if (dir == DIR_LEFT)
  {
    left = node;
  }
  else
  {
    right = node;
  }
}

template <class Y> MY_INLINE DIMENSION KDDTreeNode<Y>::next_disc () const
{
  switch (myDisc)
  {
    case DIMX: return DIMY;
    case DIMY: return DIMZ;
    default:   return DIMX;
  }
}

//- The KD_COMPARE function as defined by Samet
template <class Y> MY_INLINE DIRECTION KDDTreeNode<Y>::compare (KDDTreeNode<Y> *Q) const
{
  if (Q->myDisc == DIMX)
  {
    if (x <= Q->x) return DIR_LEFT;
    else return DIR_RIGHT;
  }
  else if (Q->myDisc == DIMY)
  {
    if (y <= Q->y) return DIR_LEFT;
    else return DIR_RIGHT;
  }
  else if (z <= Q->z)
  {
    return DIR_LEFT;
  }
  else
  {
    return DIR_RIGHT;
  }
}

//- The KD_COMPARE function as defined by Samet
template <class Y> MY_INLINE DIRECTION KDDTreeNode<Y>::compare_with_equality (KDDTreeNode<Y> *Q) const
{
  if (Q->myDisc == DIMX)
  {
    if (x < Q->x) return DIR_LEFT;
    else if (x == Q->x) return DIR_EITHER;
    else return DIR_RIGHT;
  }
  else if (Q->myDisc == DIMY)
  {
    if (y < Q->y) return DIR_LEFT;
    else if (y == Q->y) return DIR_EITHER;
    else return DIR_RIGHT;
  }
  else if (z < Q->z)
  {
    return DIR_LEFT;
  }
  else if (z == Q->z)
  {
    return DIR_EITHER;
  }
  else
  {
    return DIR_RIGHT;
  }
}