Branch data Line data Source code
1 : : //-----------------------------------------------------------------
2 : : //- Class: KDDTreeNode
3 : : //- Author: Kevin Albrecht
4 : : //- Created: 13 May 2003
5 : : //- Updated: 8 Feb 2004
6 : : //-
7 : : //- Description:
8 : : //- Node for dynamic version of the k-d tree, where k=3.
9 : : //-
10 : : //- References:
11 : : //-
12 : : //- Hanan Samet. Design and Analysis of Spatial Data Structures.
13 : : //- Addison-Wesley, Reading, MA, 1990.
14 : : //-
15 : : //- Jon Louis Bentley. Multidimensional binary search trees used
16 : : //- for associative searching. In Communications of the ACM,
17 : : //- 18(9), pages 509-517, September 1975.
18 : : //-----------------------------------------------------------------
19 : :
20 : : //---------------------------------
21 : : // Include Files
22 : : //---------------------------------
23 : :
24 : : #include "KDDTreeNode.hpp"
25 : : #include "DLIList.hpp"
26 : :
27 : : //---------------------------
28 : : // Initialize Static Members
29 : : //---------------------------
30 : :
31 : : #ifdef INLINE_TEMPLATES
32 : : #define MY_INLINE inline
33 : : #else
34 : : #define MY_INLINE
35 : : #endif
36 : :
37 : : //- Constructor
38 : 0 : template <class Y> MY_INLINE KDDTreeNode<Y>::KDDTreeNode
39 [ # # ]: 0 : ( Y aData, DIMENSION aDisc )
40 : : {
41 : 0 : parent = left = right = NULL;
42 : 0 : data = aData;
43 : :
44 [ # # ][ # # ]: 0 : boundingBox = data->bounding_box();
[ # # ]
45 [ # # ][ # # ]: 0 : x = boundingBox.center().x();
46 [ # # ][ # # ]: 0 : y = boundingBox.center().y();
47 [ # # ][ # # ]: 0 : z = boundingBox.center().z();
48 : :
49 : 0 : myDist = CUBIT_DBL_MAX;
50 : 0 : myDistData = DD_SAFETY;
51 : :
52 : 0 : myDisc = aDisc;
53 : :
54 : 0 : valid = CUBIT_TRUE;
55 : 0 : }
56 : :
57 : : //- Destructor
58 : 0 : template <class Y> MY_INLINE KDDTreeNode<Y>::~KDDTreeNode ()
59 : : {
60 [ # # ]: 0 : }
61 : :
62 : 0 : template <class Y> MY_INLINE KDDTreeNode<Y> *KDDTreeNode<Y>::get_child (DIRECTION dir) const
63 : : {
64 [ # # ]: 0 : if (dir == DIR_LEFT) return left;
65 : 0 : return right;
66 : : }
67 : :
68 : 0 : template <class Y> MY_INLINE void KDDTreeNode<Y>::set_child
69 : : ( KDDTreeNode<Y> *node,
70 : : DIRECTION dir )
71 : : {
72 [ # # ]: 0 : if (dir == DIR_LEFT)
73 : : {
74 : 0 : left = node;
75 : : }
76 : : else
77 : : {
78 : 0 : right = node;
79 : : }
80 : 0 : }
81 : :
82 : 0 : template <class Y> MY_INLINE DIMENSION KDDTreeNode<Y>::next_disc () const
83 : : {
84 [ # # # ]: 0 : switch (myDisc)
85 : : {
86 : 0 : case DIMX: return DIMY;
87 : 0 : case DIMY: return DIMZ;
88 : 0 : default: return DIMX;
89 : : }
90 : : }
91 : :
92 : : //- The KD_COMPARE function as defined by Samet
93 : 0 : template <class Y> MY_INLINE DIRECTION KDDTreeNode<Y>::compare (KDDTreeNode<Y> *Q) const
94 : : {
95 [ # # ]: 0 : if (Q->myDisc == DIMX)
96 : : {
97 [ # # ]: 0 : if (x <= Q->x) return DIR_LEFT;
98 : 0 : else return DIR_RIGHT;
99 : : }
100 [ # # ]: 0 : else if (Q->myDisc == DIMY)
101 : : {
102 [ # # ]: 0 : if (y <= Q->y) return DIR_LEFT;
103 : 0 : else return DIR_RIGHT;
104 : : }
105 [ # # ]: 0 : else if (z <= Q->z)
106 : : {
107 : 0 : return DIR_LEFT;
108 : : }
109 : : else
110 : : {
111 : 0 : return DIR_RIGHT;
112 : : }
113 : : }
114 : :
115 : : //- The KD_COMPARE function as defined by Samet
116 : 0 : template <class Y> MY_INLINE DIRECTION KDDTreeNode<Y>::compare_with_equality (KDDTreeNode<Y> *Q) const
117 : : {
118 [ # # ]: 0 : if (Q->myDisc == DIMX)
119 : : {
120 [ # # ]: 0 : if (x < Q->x) return DIR_LEFT;
121 [ # # ]: 0 : else if (x == Q->x) return DIR_EITHER;
122 : 0 : else return DIR_RIGHT;
123 : : }
124 [ # # ]: 0 : else if (Q->myDisc == DIMY)
125 : : {
126 [ # # ]: 0 : if (y < Q->y) return DIR_LEFT;
127 [ # # ]: 0 : else if (y == Q->y) return DIR_EITHER;
128 : 0 : else return DIR_RIGHT;
129 : : }
130 [ # # ]: 0 : else if (z < Q->z)
131 : : {
132 : 0 : return DIR_LEFT;
133 : : }
134 [ # # ]: 0 : else if (z == Q->z)
135 : : {
136 : 0 : return DIR_EITHER;
137 : : }
138 : : else
139 : : {
140 : 0 : return DIR_RIGHT;
141 : : }
142 : : }
143 : :
|
