Branch data Line data Source code
1 : : //---------------------------------------------------------------------------
2 : : // Class Name: RTreeNode
3 : : // Description: Node of Rectangle tree. Contians many of the
4 : : // required functions for building the tree and traversing it.
5 : : // The algorithm was taken from the following paper:
6 : : // Guttman, A., "R-Trees: A Dynamic Index Structure for
7 : : // Spatial Searching", Proceedings of the SIGMOD
8 : : // Conference, Boston, June 1984, p. 47-57.
9 : : // Creation Date: 3/13/02
10 : : // Owner: David R. White
11 : : //---------------------------------------------------------------------------
12 : : #ifndef RTREENODE_HPP
13 : : #define RTREENODE_HPP
14 : :
15 : : #include "CubitDefines.h"
16 : : #include "GeometryDefines.h"
17 : : #include "CubitBox.hpp"
18 : :
19 : : template <class X> class DLIList;
20 : : const int UNSET_RNODE = -1;
21 : : const int DATA_RNODE = 0;
22 : : const int LEAF_RNODE = 1;
23 : :
24 : : template <class Y> class RTreeNode
25 : : {
26 : : private:
27 : : //Data.
28 : : IttyBit markedFlag : 1;
29 : : IttyBit distIsBox : 1;
30 : : //Generic mark flag.
31 : : RTreeNode<Y>** myChildrenNodes;
32 : : int nextChildIndex;
33 : : CubitBox *myBoundingBox;
34 : : Y myData;
35 : : int maxChildren, minChildren; //max/min number of children.
36 : : RTreeNode<Y> *myParent;
37 : : int myLevel; //Level of node
38 : : //Level 0 equals data level.
39 : : //Level 1 equals leaf node level.
40 : : //Higher levels are non-leaf node levels.
41 : : double myDist; //used for nearest neigbhor searches...
42 : :
43 : :
44 : : //Functions.
45 : : RTreeNode<Y>* choose_leaf( RTreeNode<Y> *n, RTreeNode<Y> *e );
46 : : //- Select a leaf node in which to place
47 : : //- a new index entry e. Recursive search the subtrees of n
48 : : //- until n is a leaf node.
49 : :
50 : : CubitStatus adjust_tree(RTreeNode<Y> *l, RTreeNode<Y> *ll,
51 : : RTreeNode<Y> *root_node,
52 : : RTreeNode<Y> *&new_root);
53 : : //- Ascend from a leaf node L to the root, adjusting covering
54 : : //- bounding boxes and propagating nodes splits as necesary.
55 : :
56 : : CubitStatus quadratic_split_node( RTreeNode<Y> *l,
57 : : RTreeNode<Y> *e,
58 : : RTreeNode<Y> *&ll );
59 : : //- Since element e won't fit into l, split l into two groups, l and ll.
60 : : //- For the RTree, this is where most of the variations
61 : : //- on implementations have occured. The best method proposed by Guttman
62 : : //- was a quadratic split, which I'll implement here. The Rstar tree
63 : : //- did some slightly more complicated things which I might try later.
64 : :
65 : :
66 : : double calc_enlargement( RTreeNode<Y> *current, RTreeNode<Y> *add_to );
67 : : double calc_enlargement( CubitBox ¤t,
68 : : CubitBox &add_to );
69 : : //- Calculate the enlargement required for increasing
70 : : //- the bounding box of current so that it would encapsulate
71 : : //- the bounding box of add_to.
72 : :
73 : : CubitStatus pick_seeds(RTreeNode<Y> **input_list,
74 : : const int input_list_size,
75 : : RTreeNode<Y> *&seed_1,
76 : : RTreeNode<Y> *&seed_2);
77 : : //- Picks the two starting children of the input list that
78 : : //- are best for creating the two new groups of quadratic_split_node.
79 : :
80 : : CubitStatus pick_next(DLIList <RTreeNode<Y>*> &remaining_nodes,
81 : : RTreeNode<Y>* group_1,
82 : : RTreeNode<Y>* group_2,
83 : : RTreeNode<Y>*& next,
84 : : CubitBoolean &add_to_group_1);
85 : : //- picks one remainng entry for classification in a group. Also
86 : : //- indicates which group that should be by the add_to_group_1 flag.
87 : :
88 : : CubitStatus find_leaf( Y e,
89 : : CubitBox &e_box,
90 : : RTreeNode<Y> *t,
91 : : RTreeNode<Y> *&l );
92 : : //- find the entry e in the tree t. l
93 : : //- is the entry that contains e. (e is a data member of l).
94 : : //- The parent of l, is the leaf node containing it.
95 : :
96 : : CubitStatus condense_tree(RTreeNode<Y> *l,
97 : : RTreeNode<Y> *root,
98 : : RTreeNode<Y> *&new_root );
99 : : //- Given a leaf node l from which an entry has been deleted, eliminate
100 : : //- the node if it has too few entries and relocate its entries. Propagate
101 : : //- node elimination upaward as necessary. Adjust all covering rectangles
102 : : //- on the path to the root, making them smaller if possible.
103 : :
104 : :
105 : : double volume(CubitBox &box);
106 : : //- Calculate the volume of the box.
107 : : double volume(RTreeNode<Y>* curr);
108 : : //- Calculate the volume of the RTreeNode.
109 : :
110 : :
111 : : public:
112 : : RTreeNode(Y data, double tol, int max_children, int min_children );
113 : : RTreeNode(CubitBox &bounding_box, int max_children, int min_children);
114 : :
115 : : ~RTreeNode();
116 : : //- Constructor/Destructor
117 : :
118 : : CubitStatus insert(RTreeNode<Y> *e, RTreeNode<Y> *&new_root);
119 : : //- Inserts the node e into the proper position of this. Assumeing
120 : : //- this is the root. Sometimes the root will need to be split,
121 : : //- so a new root may be returned. If the new_root is not null,
122 : : //- then the new_root must take the place of this...
123 : :
124 : 1219 : void set_leaf_level(int r_type)
125 : 1219 : {myLevel = r_type;}
126 : : //- Set the type of level of the node.
127 : 21374 : int get_leaf_level()
128 : 21374 : {return myLevel;}
129 : : //- get the level of the node.
130 : :
131 : 184 : CubitBoolean is_leaf()
132 [ # # ][ # # ]: 184 : {return (myLevel == LEAF_RNODE)? CUBIT_TRUE : CUBIT_FALSE;}
[ # # ][ + - ]
133 : : //- Determine if the RTreeNode is a leaf node.
134 : :
135 : 29916 : CubitBoolean is_data()
136 [ + + ][ + + ]: 29916 : {return (myLevel == DATA_RNODE)? CUBIT_TRUE : CUBIT_FALSE;}
[ # # ][ + + ]
137 : : //- Determine if the RTreeNode is a leaf node.
138 : :
139 : 18367 : Y get_data()
140 : 18367 : {return myData;}
141 : : //- Determine if the RTreeNode is a leaf node.
142 : :
143 : : void add_child(RTreeNode<Y>* child_node, CubitBoolean recalc_b_box);
144 : : //- Add the child to the myChildrenNodes' list. Adds
145 : : //- it to the next availabel spot. Won't add if overflow will
146 : : //- occur.
147 : :
148 : : CubitBoolean can_add();
149 : : //- Tests if there is any space in the myChildrenNodes' list.
150 : :
151 : : int space_left();
152 : : //- Returns the number of positions left in the myChildrenNode's list.
153 : :
154 : 16947 : int num_children()
155 : 16947 : {return nextChildIndex;}
156 : : //- Returns the number of children in the myChildrenNode's array.
157 : :
158 : 67604 : RTreeNode<Y>* get_child(int i)
159 [ + - ][ + - ]: 67604 : {return ((i < nextChildIndex) ? myChildrenNodes[i] : (RTreeNode<Y>*)NULL) ;}
[ # # ][ + - ]
160 : :
161 : :
162 : : void flush(CubitBox &new_box);
163 : : //- Clears out the myChildrenNodes by setting the array values
164 : : //- to null. Resets the counters and sets the range as the new_box.
165 : :
166 : : void recalc_b_box();
167 : : //- recalculates the bounding box for the node. (won't do it if
168 : : //- this is a data node...
169 : :
170 : 2452 : RTreeNode<Y> *get_parent()
171 : 2452 : {return myParent;}
172 : 7626 : void set_parent(RTreeNode<Y> *parent)
173 : 7626 : {myParent = parent;}
174 : :
175 : : CubitBoolean remove_child(RTreeNode<Y> *child);
176 : : //- removes the child from the myChildrenNodes array and condenses
177 : : //- the array. decrements the number of children or increments the
178 : : //- num positions available.
179 : :
180 : : CubitBoolean remove(Y e, RTreeNode<Y> *&new_root, CubitBoolean &delete_root);
181 : : //- removes the data e from the tree and cleans up the tree. A new
182 : : //- root node could be found from this. Assume the root node is
183 : : //- calling this function...
184 : :
185 : 153859 : CubitBox& bounding_box()
186 : 153859 : {return *myBoundingBox;}
187 : : //- Returns the bounding box of this node.
188 : :
189 : : double get_dist();
190 : : void set_dist(double dis);
191 : :
192 : : int dist_is_box();
193 : : void set_dist_is_box(int val);
194 : :
195 : :
196 : : };
197 : 0 : template <class Y> inline int RTreeNode<Y>::dist_is_box()
198 : : {
199 : 0 : return distIsBox;
200 : : }
201 : 0 : template <class Y> inline void RTreeNode<Y>::set_dist_is_box(int val)
202 : : {
203 [ # # ][ # # ]: 0 : if ( val )
[ # # ][ # # ]
204 : 0 : distIsBox = 1;
205 : : else
206 : 0 : distIsBox = 0;
207 : 0 : }
208 : :
209 : 0 : template <class Y> inline double RTreeNode<Y>::get_dist()
210 : : {
211 : 0 : return myDist;
212 : : }
213 : 0 : template <class Y> inline void RTreeNode<Y>::set_dist(double dist)
214 : : {
215 : 0 : myDist = dist;
216 : 0 : }
217 : :
218 : : //Calculate the volume of the box.
219 : 126683 : template <class Y> inline double RTreeNode<Y>::volume(CubitBox &box)
220 : : {
221 : 126683 : return box.x_range()*box.y_range()*box.z_range();
222 : : }
223 : : //Calculate the volume of the RTreeNode.
224 : 9249 : template <class Y> inline double RTreeNode<Y>::volume(RTreeNode<Y>* curr)
225 : : {
226 [ + - ][ + - ]: 9249 : CubitBox box = curr->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
227 [ + - ][ + - ]: 9249 : return box.x_range()*box.y_range()*box.z_range();
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ + - ]
228 : : }
229 : :
230 : : #include "RTreeNode.cpp"
231 : :
232 : : #endif
233 : :
|
