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 : :
13 : : //---------------------------------
14 : : //Include Files
15 : : //---------------------------------
16 : : #include "RTreeNode.hpp"
17 : : #include "DLIList.hpp"
18 : : #include "CubitMessage.hpp"
19 : :
20 : : //---------------------------
21 : : //Initialize Static Members
22 : : //---------------------------
23 : :
24 : : #ifdef INLINE_TEMPLATES
25 : : #define MY_INLINE inline
26 : : #else
27 : : #define MY_INLINE
28 : : #endif
29 : :
30 : :
31 : 2974 : template <class Y> MY_INLINE RTreeNode<Y>::RTreeNode (Y data, double tol,
32 : : int max_children,
33 : : int min_children)
34 : : {
35 : 2974 : maxChildren = max_children;
36 : 2974 : minChildren = min_children;
37 [ + - ][ + - ]: 2974 : myChildrenNodes = new RTreeNode<Y>* [maxChildren];
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
38 : : int ii;
39 [ + + ][ + + ]: 26766 : for ( ii = 0; ii < maxChildren; ii++ )
[ # # ][ + + ]
40 : 23792 : myChildrenNodes[ii] = (RTreeNode<Y>*) NULL;
41 [ - + ][ - + ]: 2974 : if ( data == NULL )
[ # # ][ - + ]
42 : : {
43 [ # # ][ # # ]: 0 : PRINT_ERROR("Building RTree with null data is not allowed!\n");
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
44 [ # # ][ # # ]: 0 : assert(data != NULL);
[ # # ][ # # ]
45 : : }
46 : 2974 : myData = data;
47 : 2974 : myLevel = DATA_RNODE;
48 [ + - ][ + - ]: 2974 : CubitBox temp_box = data->bounding_box();
[ # # ][ + - ]
[ # # ]
49 : : //Check to see if any of the min/max pairs are less than the tolerance.
50 : : //make them bigger if they are...
51 [ + - ][ + - ]: 2974 : CubitVector min = temp_box.minimum();
[ # # ][ + - ]
52 [ + - ][ + - ]: 2974 : CubitVector max = temp_box.maximum();
[ # # ][ + - ]
53 [ + - ][ + - ]: 2974 : if ( max.x() - min.x() < tol )
[ + - ][ + - ]
[ + - ][ + + ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + + ]
54 : : {
55 [ + - ][ + - ]: 2074 : min.x(min.x()-.6*tol);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
56 [ + - ][ + - ]: 2074 : max.x(max.x()+.6*tol);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
57 : : }
58 [ + - ][ + - ]: 2974 : if ( max.y() - min.y() < tol )
[ + - ][ + - ]
[ + - ][ + + ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + + ]
59 : : {
60 [ + - ][ + - ]: 1942 : min.y(min.y()-.6*tol);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
61 [ + - ][ + - ]: 1942 : max.y(max.y()+.6*tol);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
62 : : }
63 [ + - ][ + - ]: 2974 : if ( max.z() - min.z() < tol )
[ + - ][ + - ]
[ + - ][ + + ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + + ]
64 : : {
65 [ + - ][ + - ]: 2024 : min.z(min.z()-.6*tol);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
66 [ + - ][ + - ]: 2024 : max.z(max.z()+.6*tol);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
67 : : }
68 [ + - ][ + - ]: 2974 : myBoundingBox = new CubitBox(min, max);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
69 : 2974 : myParent = NULL;
70 : 2974 : nextChildIndex = 0;
71 : 2974 : markedFlag = 0;
72 : 2974 : distIsBox = 1;
73 [ + - ][ + - ]: 2974 : myDist = CUBIT_DBL_MAX;
[ # # ][ + - ]
74 : 2974 : }
75 : 715 : template <class Y> MY_INLINE RTreeNode<Y>::RTreeNode (CubitBox &bounding_box,
76 : : int max_children,
77 : : int min_children)
78 : : {
79 : 715 : maxChildren = max_children;
80 : 715 : minChildren = min_children;
81 [ + - ][ + - ]: 715 : myBoundingBox = new CubitBox(bounding_box);
[ # # ][ + - ]
82 [ + - ][ + - ]: 715 : myChildrenNodes = new RTreeNode<Y>* [maxChildren];
[ # # ][ + - ]
83 : : int ii;
84 [ + + ][ + + ]: 6435 : for ( ii = 0; ii < maxChildren; ii++ )
[ # # ][ + + ]
85 : 5720 : myChildrenNodes[ii] = (RTreeNode<Y>*) NULL;
86 : 715 : myData = NULL;
87 : 715 : myLevel = UNSET_RNODE;
88 : 715 : myParent = NULL;
89 : 715 : nextChildIndex = 0;
90 : 715 : markedFlag = 0;
91 : 715 : distIsBox = 1;
92 : 715 : myDist = CUBIT_DBL_MAX;
93 : 715 : }
94 : : //-----------------------------------------------------------
95 : : // Destructor
96 : : //-----------------------------------------------------------
97 : 3689 : template <class Y> MY_INLINE RTreeNode<Y>::~RTreeNode()
98 : : {
99 [ + - ][ + - ]: 3689 : if ( myChildrenNodes )
[ # # ][ + - ]
100 [ + - ][ + - ]: 3689 : delete [] myChildrenNodes;
[ # # ][ + - ]
101 [ + - ][ + - ]: 3689 : if ( myBoundingBox )
[ # # ][ + - ]
102 [ + - ][ + - ]: 3689 : delete myBoundingBox;
[ # # ][ + - ]
103 : 3689 : }
104 : :
105 : : //-----------------------------------------------------------
106 : : // Algorithm: insert
107 : : // Insert a new index entry e into an R-Tree.
108 : : // I1. [Find postiion for new record] Invoke choose_leaf to select
109 : : // a leaf node in l, in which to place e.
110 : : // I2. [Add record to leaf node].a) If l has room for
111 : : // another entry, install E. b) Otherwise invoke split_node to
112 : : // obtain l and ll containing e and all the old entries of l.
113 : : // I3. [Propogate changes upward] Invoke adjust_tree on l, also passing ll
114 : : // if a split was performed.
115 : : // I4. [Grow Tree Taller] If node split propogation caused the root
116 : : // to split create a new root whose children are the two resulting
117 : : // nodes.
118 : : //-----------------------------------------------------------
119 : 2974 : template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::insert(RTreeNode<Y> *e, RTreeNode<Y> *&new_root)
120 : : {
121 : : CubitStatus stat;
122 : 2974 : new_root = NULL;//only set this if the root node changes. Assume
123 : : //that this RTreeNode object is the root...
124 : :
125 : :
126 : : // I1. Invoke choose_leaf to select a leaf node l in which to place
127 : : //e
128 [ + - ][ + - ]: 2974 : RTreeNode<Y> *l = choose_leaf(this, e);
[ # # ][ + - ]
129 : : //just test.
130 : : // make sure l is not null.
131 : : // make sure l is one level above e.
132 [ + - ][ + - ]: 2974 : if ( l == NULL || l->get_leaf_level() != (e->get_leaf_level() + 1) )
[ + - ][ - + ]
[ - + ][ + - ]
[ + - ][ + - ]
[ - + ][ - + ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
[ - + ][ - + ]
133 : : {
134 [ # # ][ # # ]: 0 : PRINT_ERROR("Choosing leaf for inseartion into rtree failed.\n");
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
135 : 0 : return CUBIT_FAILURE;
136 : : }
137 : 2974 : RTreeNode<Y> *ll = NULL;
138 : : //I2 a) If l has room for another entry install e.
139 [ + - ][ + + ]: 2974 : if ( l->can_add() )
[ + - ][ + + ]
[ # # ][ # # ]
[ + - ][ + + ]
140 : : {
141 [ + - ][ + - ]: 2501 : l->add_child(e, CUBIT_TRUE);
[ # # ][ + - ]
142 : : }
143 : : else
144 : : {
145 : : //I2 b)
146 : : //Otherwise invoke split_node to obtain l and ll containing e and
147 : : //all the old entries of l.
148 [ + - ][ + - ]: 473 : stat = quadratic_split_node(l,e,ll);
[ # # ][ + - ]
149 [ + - ][ - + ]: 473 : if ( stat != CUBIT_SUCCESS || ll == NULL )
[ + - ][ - + ]
[ # # ][ # # ]
[ + - ][ - + ]
150 : : {
151 [ # # ][ # # ]: 0 : PRINT_ERROR("Problems splitting node during insertion to RTree.\n");
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
152 : 0 : return CUBIT_FAILURE;
153 : : }
154 : : }
155 : : //I3. Propagate changes upward.
156 : : //I4, grow tree taller (do both inside adjust_tree...)
157 [ + - ][ + - ]: 2974 : stat = adjust_tree(l, ll, this, new_root);
[ # # ][ + - ]
158 [ - + ][ - + ]: 2974 : if ( stat!= CUBIT_SUCCESS )
[ # # ][ - + ]
159 : 0 : return stat;
160 : 2974 : return CUBIT_SUCCESS;
161 : : }
162 : :
163 : : //--------------------------------------------
164 : : // Algorithm: ChooseLeaf: Select a leaf node in which to place
165 : : // a new index entry e. Recursive search the subtrees of n
166 : : // until n is a leaf node.
167 : : //----------------------------------------------
168 : 5262 : template <class Y> MY_INLINE RTreeNode<Y>* RTreeNode<Y>::choose_leaf( RTreeNode<Y>* n,
169 : : RTreeNode<Y>* e )
170 : : {
171 : : //If n is a leaf node, or one level greater than e,
172 : : //we are done.
173 [ + + ][ + + ]: 5262 : if ( n->get_leaf_level() == (e->get_leaf_level() + 1) )
[ # # ][ + + ]
174 : 2974 : return n;
175 : : //Now choose the entry f in n (children of n that is)
176 : : //whose bounding box f_box needs
177 : : //least enlargement to include e_box. Resolve ties by
178 : : //choosing the entry with the bounding box of smallest volume.
179 : 2288 : double min_enlargement = CUBIT_DBL_MAX, curr_enlargement;
180 : : RTreeNode<Y> *curr_node;
181 : 2288 : int child_index = -1;
182 : : int ii;
183 [ + - ][ + + ]: 11161 : for(ii = 0; (ii < maxChildren) && (n->myChildrenNodes[ii] != NULL); ii++ )
[ + + ][ + + ]
[ # # ][ # # ]
[ + - ][ + + ]
184 : : {
185 : :
186 : 8873 : curr_node = n->myChildrenNodes[ii];
187 : 8873 : curr_enlargement = calc_enlargement(curr_node, e);
188 [ + + + + : 8873 : if ( curr_enlargement <= min_enlargement )
# # + + ]
189 : : {
190 [ - + ][ # # ]: 4950 : if ( curr_enlargement == min_enlargement && child_index >= 0 )
[ + + ][ + - ]
[ # # ][ # # ]
[ + + ][ + - ]
191 : : {
192 : : //only reset if the curr_node has a smaller volume.
193 : 188 : double curr_vol = volume(curr_node);
194 : 188 : double old_vol = volume(n->myChildrenNodes[child_index]);
195 [ # # + + : 188 : if ( old_vol < curr_vol )
# # + + ]
196 : 188 : continue;
197 : : }
198 : 4909 : child_index = ii;
199 : 4909 : min_enlargement = curr_enlargement;
200 : : }
201 : : }
202 : : //do error checking...
203 [ + - ][ - + ]: 2288 : if ( child_index == -1 || child_index >= maxChildren )
[ + - ][ - + ]
[ # # ][ # # ]
[ + - ][ - + ]
204 : 0 : return (RTreeNode<Y>*)NULL;
205 : 2288 : RTreeNode<Y> *f = n->myChildrenNodes[child_index];
206 : : //Now continue on...
207 : 2288 : curr_node = choose_leaf(f,e);
208 : 2288 : return curr_node;
209 : : }
210 : : //----------------------------------------------------------------------
211 : : // calc_enlargement: Calculate the enlargement required for increasing
212 : : // the bounding box of current so that it would encapsulate the bounding
213 : : // box of add_to. So to do that, create the union of the two bounding
214 : : // boxes, then of that supper box subtrace the volume of the current.
215 : : // The result should be the volumetric difference between how much
216 : : // current has and how much it would need be or the enlargement.
217 : : //----------------------------------------------------------------------
218 : 8873 : template <class Y> MY_INLINE double RTreeNode<Y>::calc_enlargement(RTreeNode<Y> *current, RTreeNode<Y> *add_to )
219 : : {
220 : : //The enlargement area is the volume of the box that would
221 : : //be the union of current and add_to minus the volume of the current.
222 [ + - ][ + - ]: 8873 : CubitBox curr_box = current->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
223 [ + - ][ + - ]: 17746 : CubitBox add_to_box = add_to->bounding_box();
[ + - ][ + - ]
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
224 [ + - ][ + - ]: 17746 : CubitBox supper = curr_box;
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
225 : : //Unite add_to_box to the curr_box.
226 [ + - ][ + - ]: 8873 : supper|= add_to_box;
[ # # ][ + - ]
227 [ + - ][ + - ]: 8873 : double area_big = volume(supper);
[ # # ][ + - ]
228 [ + - ][ + - ]: 17746 : return area_big - volume(current);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
229 : : }
230 : 28182 : template <class Y> MY_INLINE double RTreeNode<Y>::calc_enlargement(CubitBox ¤t, CubitBox &add_to )
231 : : {
232 : : //The enlargement area is the volume of the box that would
233 : : //be the union of current and add_to minus the volume of the current.
234 [ + - ][ + - ]: 28182 : CubitBox supper = current;
[ # # ][ + - ]
235 : : // unite the add_to box.
236 [ + - ][ + - ]: 28182 : supper |= add_to;
[ # # ][ + - ]
237 [ + - ][ + - ]: 28182 : double area_big = volume(supper);
[ # # ][ + - ]
238 [ + - ][ + - ]: 28182 : return area_big - volume(current);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
239 : : }
240 : : //------------------------------------------------------------------
241 : : // Algorithm: adjust_tree
242 : : // Description: Ascend from a leaf node L to the root, adjusting covering
243 : : // bounding boxes and propagating nodes splits as necesary.
244 : : //------------------------------------------------------------------
245 : 5262 : template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::adjust_tree(RTreeNode<Y> *l, RTreeNode<Y> *ll,
246 : : RTreeNode<Y> *root_node,
247 : : RTreeNode<Y> *&new_root)
248 : : {
249 : : CubitStatus stat;
250 : : //we need to move up the tree and correct things that have changed.
251 [ + + ][ + + ]: 5262 : if ( l == root_node )
[ # # ][ + + ]
252 : : {
253 [ + + ][ + + ]: 2974 : if ( ll == NULL )
[ # # ][ + + ]
254 : 2858 : return CUBIT_SUCCESS;
255 : : else
256 : : {
257 : : //Create a new root node and store l and ll there
258 [ + - ][ + - ]: 116 : CubitBox root_box = l->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
259 [ + - ][ + - ]: 116 : root_box |= ll->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
260 [ + - ][ + - ]: 116 : new_root = new RTreeNode<Y>(root_box, maxChildren, minChildren);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
261 [ + - ][ + - ]: 116 : int new_level = l->get_leaf_level() + 1;
[ # # ][ + - ]
262 [ + - ][ + - ]: 116 : new_root->set_leaf_level(new_level);
[ # # ][ + - ]
263 [ + - ][ + - ]: 116 : new_root->add_child(l, CUBIT_TRUE);
[ # # ][ + - ]
264 [ + - ][ + - ]: 116 : new_root->add_child(ll, CUBIT_TRUE);
[ # # ][ + - ]
265 [ + - ][ + - ]: 116 : return CUBIT_SUCCESS;
[ # # ][ + - ]
266 : : }
267 : : }
268 [ + - ][ + - ]: 2288 : RTreeNode<Y> *parent_node = l->get_parent();
[ # # ][ + - ]
269 : 2288 : RTreeNode<Y> *new_group = NULL;
270 [ + + ][ + + ]: 2288 : if ( ll != NULL )
[ # # ][ + + ]
271 : : {
272 : : //We need to add ll to the parent if we can,
273 : : //and then we need to update the parent's bounding box...
274 [ + - ][ + - ]: 388 : if ( parent_node->can_add() )
[ + - ][ + + ]
[ # # ][ # # ]
[ + - ][ + - ]
275 : : {
276 [ + - ][ + - ]: 357 : parent_node->add_child(ll, CUBIT_FALSE);
[ # # ][ + - ]
277 : : //we need to recalculate the bounding box for the
278 : : //entire set since both l and ll were modified...
279 [ + - ][ + - ]: 357 : parent_node->recalc_b_box();
[ # # ][ + - ]
280 : : }
281 : : else
282 : : {
283 : : //Now we must split the children of the parent. l should
284 : : //already be in the chilren list of the paretn. So send
285 : : //to split node the parent_node and ll.
286 : : //parent node during this process will have its b_box recalced.
287 [ # # ][ + - ]: 31 : stat = quadratic_split_node(parent_node, ll, new_group);
[ # # ][ # # ]
288 [ # # ][ # # ]: 31 : if ( stat != CUBIT_SUCCESS || new_group == NULL )
[ + - ][ - + ]
[ # # ][ # # ]
[ # # ][ # # ]
289 : : {
290 [ # # ][ # # ]: 0 : PRINT_ERROR("Problems splitting node during insertion to RTree.\n");
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
291 : 0 : return CUBIT_FAILURE;
292 : : }
293 : : }
294 : : }
295 : : else
296 : : {
297 : : //just recalulate the b_box for the parent_node.
298 [ + - ][ + - ]: 1900 : parent_node->recalc_b_box();
[ # # ][ + - ]
299 : : }
300 [ + - ][ + - ]: 2288 : stat = adjust_tree(parent_node, new_group, root_node, new_root);
[ # # ][ + - ]
301 [ - + ][ - + ]: 2288 : if ( stat != CUBIT_SUCCESS )
[ # # ][ - + ]
302 : 0 : return CUBIT_FAILURE;
303 : 5262 : return CUBIT_SUCCESS;
304 : : }
305 : : //------------------------------------------------------------------
306 : : // Algorithm: quadratic_split_node
307 : : // Description: For the RTree, this is where most of the variations
308 : : // on implementations have occured. The best method proposed by Guttman
309 : : // was a quadratic split, which I'll implement here. The Rstar tree
310 : : // did some slightly more complicated things which I might try later.
311 : : // Description of function:
312 : : // e is the node to which we want to add l, but l's children's list
313 : : // is full. Split the children of l and e up into two groups. The
314 : : // groups are stored in l and ll.
315 : : // Assume: assume that l's myChildrenNodes are maxChildren in size.
316 : : //
317 : : // Divide a set of maxChildren + 1 index entries into two groups.
318 : : // QS1 [Pick first entry for each group] Apply algorithm pick_seeds,
319 : : // to choose two entries to be the first elements of the groups.
320 : : // Assign each to a group.
321 : : // QS2 [Check if done] If all entries have been assigned, stop.
322 : : // If one group has so few entries that all the rest must
323 : : // be assigned to it in order for it to have the minimum number m,
324 : : // assign them and stop.
325 : : // QS3 [Select entry to assign] Invoke Algorithm pick_next to choose
326 : : // the next entry to assign. Add it to the group whose covering
327 : : // rectangle will have to be enlarged least to accommodate it.
328 : : // Resolve ties by adding the entry to the group with the smaller
329 : : // volume, then to the one with fewer entries, then to either. Repeat
330 : : // QS2.
331 : : //
332 : : //------------------------------------------------------------------
333 : 504 : template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::quadratic_split_node( RTreeNode<Y> *l,
334 : : RTreeNode<Y> *e,
335 : : RTreeNode<Y> *&ll )
336 : : {
337 : : int ii;
338 : : //create a new list containing all the nodes we want to split.
339 [ + - ][ + - ]: 504 : RTreeNode<Y> **input_list = new RTreeNode<Y>* [maxChildren + 1];
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
340 [ + - ][ + - ]: 504 : DLIList <RTreeNode<Y>*> nodes_remaining;
[ # # ][ + - ]
341 [ + + ][ + + ]: 4536 : for ( ii = 0; ii < maxChildren; ii++ )
[ # # ][ + + ]
342 : : {
343 : 4032 : input_list[ii] = l->myChildrenNodes[ii];
344 : : }
345 : 504 : input_list[maxChildren] = e;
346 : :
347 : : //QS1, pick first entry for each group.
348 : : RTreeNode<Y> *seed_1, *seed_2;
349 : : CubitStatus stat = pick_seeds(input_list, maxChildren+1,seed_1,
350 [ + - ][ + - ]: 504 : seed_2);
[ # # ][ + - ]
351 [ - + ][ - + ]: 504 : if ( stat != CUBIT_SUCCESS )
[ # # ][ - + ]
352 : : {
353 [ # # ][ # # ]: 0 : delete [] input_list;
[ # # ][ # # ]
354 : 0 : return stat;
355 : : }
356 : : //now flush out l. This cleans out the bounding box and
357 : : //chindrenNodes and resets the bounding box. Also
358 : : //create ll, make l and ll non-leaf nodes and add
359 : : //seed_1 and seed_2 to l and ll. (doesn't matter which...)
360 [ + - ][ + - ]: 504 : l->flush(seed_1->bounding_box());
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
361 [ + - ][ + - ]: 504 : l->add_child(seed_1, CUBIT_FALSE);
[ # # ][ + - ]
362 : : //this is still a leaf node.
363 : : //this will change if necessary the parent...
364 [ + - ][ + - ]: 504 : l->set_leaf_level(e->get_leaf_level() + 1);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
365 [ + - ][ + - ]: 504 : ll = new RTreeNode<Y>(seed_2->bounding_box(), maxChildren, minChildren );
[ + - ][ + - ]
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
366 [ + - ][ + - ]: 504 : ll->add_child(seed_2, CUBIT_FALSE);
[ # # ][ + - ]
367 [ + - ][ + - ]: 504 : ll->set_leaf_level(l->get_leaf_level());
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
368 : : //build the nodes remaining list...
369 [ + + ][ + + ]: 5040 : for ( ii = 0; ii < maxChildren+1; ii++ )
[ # # ][ + + ]
370 : : {
371 [ + + ][ + + ]: 4536 : if ( input_list[ii] != seed_1 &&
[ + + ][ + + ]
[ # # ][ # # ]
[ + + ][ + + ]
372 : 4032 : input_list[ii] != seed_2 )
373 [ + - ][ + - ]: 3528 : nodes_remaining.append(input_list[ii]);
[ # # ][ + - ]
374 : : }
375 [ + - ][ + - ]: 504 : delete [] input_list;
[ # # ][ + - ]
376 : : RTreeNode<Y> *next_node;
377 : : CubitBoolean add_to_group_1;
378 : : //Q2
379 [ + - ][ + + ]: 4011 : while (nodes_remaining.size() > 0 )
[ + - ][ + + ]
[ # # ][ # # ]
[ + - ][ + + ]
380 : : {
381 : : //Q2 continued.
382 [ + - ][ - + ]: 3539 : if ( l->space_left() < minChildren &&
[ # # ][ - + ]
[ + - ][ + + ]
[ + - ][ + + ]
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ - + ]
[ # # ][ - + ]
383 [ # # ][ # # ]: 11 : minChildren - l->space_left() >= nodes_remaining.size() )
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ # # ]
384 : : {
385 : : //just add the rest of the nodes to l.
386 [ # # ][ # # ]: 22 : for ( ii = nodes_remaining.size(); ii > 0; ii-- )
[ + - ][ + + ]
[ # # ][ # # ]
[ # # ][ # # ]
387 [ # # ][ # # ]: 11 : l->add_child(nodes_remaining.get_and_step(), CUBIT_TRUE);
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ # # ]
388 [ # # ][ + - ]: 11 : nodes_remaining.clean_out();
[ # # ][ # # ]
389 : 11 : break;
390 : : }
391 [ + - ][ - + ]: 3527 : else if ( ll->space_left() < minChildren &&
[ # # ][ - + ]
[ + - ][ + + ]
[ + - ][ + + ]
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ - + ]
[ # # ][ - + ]
392 [ # # ][ # # ]: 10 : minChildren - ll->space_left() >= nodes_remaining.size() )
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ # # ]
393 : : {
394 : : //just add the rest of the nodes to l.
395 [ # # ][ # # ]: 20 : for ( ii = nodes_remaining.size(); ii > 0; ii-- )
[ + - ][ + + ]
[ # # ][ # # ]
[ # # ][ # # ]
396 [ # # ][ # # ]: 10 : ll->add_child(nodes_remaining.get_and_step(), CUBIT_TRUE);
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ # # ]
397 [ # # ][ + - ]: 10 : nodes_remaining.clean_out();
[ # # ][ # # ]
398 : 10 : break;
399 : : }
400 : : //Q3
401 : : //pick next selects the next node and the group to
402 : : //put it in. It also removes the node from nodes remaining.
403 : : //Some of these steps were added to pick next for efficiency...
404 [ + - ][ + - ]: 3507 : stat = pick_next(nodes_remaining, l, ll, next_node,
[ # # ][ + - ]
405 : 3507 : add_to_group_1 );
406 [ - + ][ - + ]: 3507 : if ( stat != CUBIT_SUCCESS )
[ # # ][ - + ]
407 : 0 : return stat;
408 [ + + ][ + + ]: 3507 : if ( add_to_group_1 )
[ # # ][ + + ]
409 [ + - ][ + - ]: 1806 : l->add_child(next_node, CUBIT_TRUE);
[ # # ][ + - ]
410 : : else
411 [ + - ][ + - ]: 1701 : ll->add_child(next_node, CUBIT_TRUE);
[ # # ][ + - ]
412 : : }
413 [ + - ][ + - ]: 504 : return CUBIT_SUCCESS;
[ # # ][ + - ]
414 : : }
415 : 504 : template <class Y> MY_INLINE void RTreeNode<Y>::flush( CubitBox &new_box )
416 : : {
417 : : int ii;
418 : 504 : nextChildIndex = 0;
419 [ + + ][ + + ]: 4536 : for ( ii = 0; ii < maxChildren; ii++ )
[ # # ][ + + ]
420 : 4032 : myChildrenNodes[ii] = NULL;
421 [ + - ][ + - ]: 504 : delete myBoundingBox;
[ # # ][ + - ]
422 [ + - ][ + - ]: 504 : myBoundingBox = new CubitBox(new_box);
[ # # ][ + - ]
423 : 504 : }
424 : 7626 : template <class Y> MY_INLINE void RTreeNode<Y>::add_child(RTreeNode<Y> *child_node,
425 : : CubitBoolean recalc_b_box)
426 : : {
427 [ + - ][ - + ]: 7626 : assert(nextChildIndex < maxChildren && child_node != NULL );
[ + - ][ - + ]
[ # # ][ # # ]
[ + - ][ - + ]
428 : 7626 : myChildrenNodes[nextChildIndex] = child_node;
429 : : //update the bounding box. by uniting with child node...
430 [ + + ][ + + ]: 7626 : if ( recalc_b_box )
[ # # ][ + + ]
431 : : {
432 : 6261 : CubitBox *old_box = myBoundingBox;
433 [ + - ][ + - ]: 6261 : myBoundingBox = new CubitBox( *old_box |= child_node->bounding_box());
[ # # ][ + - ]
434 [ + - ][ + - ]: 6261 : delete old_box;
[ # # ][ + - ]
435 : : }
436 : 7626 : nextChildIndex++;
437 : 7626 : child_node->set_parent(this);
438 : 7626 : }
439 : 3362 : template <class Y> MY_INLINE CubitBoolean RTreeNode<Y>::can_add()
440 : : {
441 [ + + ][ + + ]: 3362 : if (nextChildIndex >= maxChildren )
[ # # ][ + + ]
442 : 504 : return CUBIT_FALSE;
443 : : else
444 : 2858 : return CUBIT_TRUE;
445 : : }
446 : 7352 : template <class Y> MY_INLINE int RTreeNode<Y>::space_left()
447 : : {
448 : 7352 : return maxChildren - nextChildIndex;
449 : : }
450 : : //------------------------------------------------------------------
451 : : // Algorithm pick_seeds:
452 : : // Select two entries to be the first elements of the groups.
453 : : // PS1 [Calculate inefficiency of grouping entries together] For
454 : : // each pair of entries, e1 and e2, compose a rectangle (bounding_box)
455 : : // j, including e1 and e2, calculate:
456 : : // d = volume(j) - volume(e1) - volume(e2)
457 : : // PS2 [Choose the most wasteful pair] Choose the pair with the largest
458 : : // d.
459 : : //------------------------------------------------------------------
460 : 504 : template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::pick_seeds(RTreeNode<Y> **input_list,
461 : : const int input_list_size,
462 : : RTreeNode<Y> *&seed_1,
463 : : RTreeNode<Y> *&seed_2)
464 : : {
465 : : int ii, jj;
466 : : RTreeNode<Y> *e_1, *e_2;
467 [ + - ][ + - ]: 1008 : CubitBox e_box_1, e_box_2, j;
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
468 : 504 : double d, max_d = -CUBIT_DBL_MAX;
469 : 504 : seed_1 = (RTreeNode<Y>*)NULL;
470 : 504 : seed_2 = (RTreeNode<Y>*)NULL;
471 : :
472 [ + + ][ + + ]: 5040 : for(ii = 0; ii < input_list_size; ii++ )
[ # # ][ + + ]
473 : : {
474 : 4536 : e_1 = input_list[ii];
475 [ + - ][ + - ]: 4536 : e_box_1 = e_1->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
476 [ + + ][ + + ]: 22680 : for ( jj = ii+1; jj < input_list_size; jj++ )
[ # # ][ + + ]
477 : : {
478 : 18144 : e_2 = input_list[jj];
479 [ + - ][ + - ]: 18144 : e_box_2 = e_2->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
480 : : //unite the boxes.
481 [ + - ][ + - ]: 18144 : j = e_box_1;
[ # # ][ + - ]
482 [ + - ][ + - ]: 18144 : j |= e_box_2;
[ # # ][ + - ]
483 : : //find the most wastefull boxes to separate the groups.
484 [ + - ][ + - ]: 18144 : d = volume(j) - volume(e_box_1) - volume(e_box_2);
[ + - ][ + - ]
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
485 [ + + ][ + + ]: 18144 : if ( d > max_d )
[ # # ][ + + ]
486 : : {
487 : 1966 : seed_1 = e_1;
488 : 1966 : seed_2 = e_2;
489 : 1966 : max_d = d;
490 : : }
491 : : }
492 : : }
493 [ + - ][ + - ]: 504 : return CUBIT_SUCCESS;
[ # # ][ + - ]
494 : : }
495 : : //------------------------------------------------------------------
496 : : // Algorithm pick_next:
497 : : // Select one remaining entry for classification in a group.
498 : : // PN1 [Determine cost of putting each entry in group] For each entry
499 : : // e not yet in a group, calculate d1 = area increase required in the
500 : : // covering rectangle of group_1 to include E. Calculate d2 similarly
501 : : // for group_2
502 : : // PN2 [Find entry with greatest preference for one group] Choose
503 : : // any entry with the maximum difference between d1 and d2.
504 : : //------------------------------------------------------------------
505 : 3507 : template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::pick_next(DLIList <RTreeNode<Y>*> &remaining_nodes,
506 : : RTreeNode<Y>* group_1,
507 : : RTreeNode<Y>* group_2,
508 : : RTreeNode<Y>*& next,
509 : : CubitBoolean &add_to_group_1)
510 : : {
511 : 3507 : int ii, next_index = 0;
512 : 3507 : double d1, d2, max_diff = -CUBIT_DBL_MAX;
513 : 3507 : add_to_group_1 = CUBIT_TRUE;
514 : 3507 : RTreeNode<Y> *max_diff_node = (RTreeNode<Y>*)NULL;
515 : : RTreeNode<Y> *curr_node;
516 [ + - ][ + - ]: 3507 : CubitBox group_1_box = group_1->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
517 [ + - ][ + - ]: 7014 : CubitBox group_2_box = group_2->bounding_box();
[ + - ][ + - ]
[ + - ][ + - ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
518 [ + - ][ + - ]: 7014 : CubitBox curr_box;
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
519 [ + - ][ + - ]: 3507 : double v1 = volume(group_1_box);
[ # # ][ + - ]
520 [ + - ][ + - ]: 3507 : double v2 = volume(group_2_box);
[ # # ][ + - ]
521 [ + - ][ + - ]: 3507 : remaining_nodes.reset();
[ # # ][ + - ]
522 [ + - ][ + + ]: 17598 : for ( ii = 0; ii < remaining_nodes.size(); ii++ )
[ + - ][ + + ]
[ # # ][ # # ]
[ + - ][ + + ]
523 : : {
524 [ + - ][ + - ]: 14091 : curr_node = remaining_nodes.get_and_step();
[ # # ][ + - ]
525 [ + - ][ + - ]: 14091 : curr_box = curr_node->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
526 [ + - ][ + - ]: 14091 : d1 = calc_enlargement(group_1_box, curr_box);
[ # # ][ + - ]
527 [ + - ][ + - ]: 14091 : d2 = calc_enlargement(group_2_box, curr_box);
[ # # ][ + - ]
528 [ + + ][ + + ]: 14091 : if ( d1 > d2 )
[ # # ][ + + ]
529 : : {
530 [ + + ][ + + ]: 6443 : if ( max_diff < d1 - d2 )
[ # # ][ + + ]
531 : : {
532 : : //add to group whose covering area would have
533 : : //to be enlarged least.
534 : 2822 : add_to_group_1 = CUBIT_FALSE;
535 : 2822 : max_diff = d1 - d2;
536 : 2822 : max_diff_node = curr_node;
537 : 2822 : next_index = ii;
538 : : }
539 : : }
540 [ + + ][ + + ]: 7648 : else if ( d2 > d1 )
[ # # ][ + + ]
541 : : {
542 [ + + ][ + + ]: 7031 : if ( max_diff < d2 - d1 )
[ # # ][ + + ]
543 : : {
544 : : //add to group whose covering area would have
545 : : //to be enlarged least.
546 : 3614 : add_to_group_1 = CUBIT_TRUE;
547 : 3614 : max_diff = d2 - d1;
548 : 3614 : max_diff_node = curr_node;
549 : 3614 : next_index = ii;
550 : : }
551 : : }
552 : : else {
553 [ + + ][ + + ]: 617 : if ( max_diff < 0.0 )
[ # # ][ + + ]
554 : : {
555 : : //Add to group with smaller area.
556 [ + + ][ + + ]: 165 : if ( v1 < v2 )
[ # # ][ - + ]
557 : 22 : add_to_group_1 = CUBIT_TRUE;
558 [ - + ][ - + ]: 143 : else if ( v2 < v1 )
[ # # ][ - + ]
559 : 0 : add_to_group_1 = CUBIT_FALSE;
560 : : else
561 : : {
562 : : //add to group with fewest entries.
563 [ + - ][ + - ]: 143 : int num_left_1 = group_1->space_left();
[ # # ][ + - ]
564 [ + - ][ + - ]: 143 : int num_left_2 = group_2->space_left();
[ # # ][ + - ]
565 [ - + ][ - + ]: 143 : if ( num_left_1 > num_left_2 )
[ # # ][ + + ]
566 : 10 : add_to_group_1 = CUBIT_TRUE;
567 : : else
568 : 133 : add_to_group_1 = CUBIT_FALSE;
569 : : }
570 : 165 : max_diff = 0.0;
571 : 165 : max_diff_node = curr_node;
572 : 165 : next_index = ii;
573 : : }
574 : : }
575 : : }
576 : 3507 : next = NULL;
577 [ - + ][ - + ]: 3507 : if ( max_diff_node == NULL )
[ # # ][ - + ]
578 : 0 : return CUBIT_FAILURE;
579 : : else
580 : 3507 : next = max_diff_node;
581 : : //remove next from the remaining_nodes list.
582 [ + - ][ + - ]: 3507 : remaining_nodes.reset();
[ # # ][ + - ]
583 [ + - ][ + - ]: 3507 : remaining_nodes.step(next_index);
[ # # ][ + - ]
584 [ + - ][ + - ]: 3507 : RTreeNode<Y> *check_node = remaining_nodes.remove();
[ # # ][ + - ]
585 [ - + ][ - + ]: 3507 : if ( check_node != max_diff_node )
[ # # ][ - + ]
586 : : {
587 [ # # ][ # # ]: 0 : PRINT_ERROR("Error in pick next algorithm logic of rtree...");
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
588 : 0 : return CUBIT_FAILURE;
589 : : }
590 [ + - ][ + - ]: 7014 : return CUBIT_SUCCESS;
[ # # ][ + - ]
591 : : }
592 : 2339 : template <class Y> MY_INLINE void RTreeNode<Y>::recalc_b_box()
593 : : {
594 [ - + ][ - + ]: 2339 : if(myLevel == DATA_RNODE )
[ # # ][ - + ]
595 : 0 : return;
596 : : int ii;
597 [ + - ][ + - ]: 2339 : CubitBox temp_box;
[ # # ][ + - ]
598 : 2339 : CubitBoolean first_box = CUBIT_TRUE;
599 [ + + ][ + + ]: 11674 : for ( ii = 0; ii < nextChildIndex; ii++ )
[ # # ][ + + ]
600 : : {
601 [ + + ][ + + ]: 9335 : if ( first_box )
[ # # ][ + + ]
602 : : {
603 [ + - ][ + - ]: 2339 : temp_box = myChildrenNodes[ii]->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
604 : 2339 : first_box = CUBIT_FALSE;
605 : : }
606 : : else
607 [ + - ][ + - ]: 6996 : temp_box |= myChildrenNodes[ii]->bounding_box();
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
608 : : }
609 [ + - ][ + - ]: 2339 : delete myBoundingBox;
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
610 [ + - ][ + - ]: 2339 : myBoundingBox = new CubitBox(temp_box);
[ + - ][ + - ]
[ # # ][ # # ]
[ + - ][ + - ]
611 [ + - ][ + - ]: 2339 : return;
[ # # ][ + - ]
612 : : }
613 : : //-------------------------------------------------------------
614 : : // Algorithm: remove. Remove index record e from an R-tree.
615 : : // D1) [Find node containing record]. Invoke find_leaf to locate
616 : : // the leaf node l containing e. Stop if the record was not
617 : : // found.
618 : : // D2) [Delete record.] Remove e from l.
619 : : // D3) [Propagate changes.] Invoke CondenseTree, passing L.
620 : : // D4) [Shorten tree.] If the root node has only one child
621 : : // after the tree has been adjusted, make the child the new
622 : : // root.
623 : : //-------------------------------------------------------------
624 : 82 : template <class Y> MY_INLINE CubitBoolean RTreeNode<Y>::remove( Y e,
625 : : RTreeNode<Y> *&new_root,
626 : : CubitBoolean &delete_root)
627 : : {
628 : : //D1) Find node containting record.
629 [ # # ][ # # ]: 82 : if(this->is_data()){
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ - + ]
630 [ # # ][ # # ]: 0 : if(this->get_data() == e){
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
631 : 0 : myData = NULL;
632 : 0 : myLevel = UNSET_RNODE;
633 : 0 : return CUBIT_TRUE;
634 : : }
635 [ # # ][ # # ]: 0 : else if(this->num_children() == 0){
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
636 : 0 : return CUBIT_FALSE;
637 : : }
638 : : }
639 : 82 : RTreeNode<Y> *l = NULL;
640 [ # # ][ # # ]: 82 : CubitBox my_box = e->bounding_box();
[ # # ][ + - ]
[ # # ]
641 [ # # ][ # # ]: 82 : CubitStatus stat = find_leaf(e, my_box, this, l);
[ # # ][ + - ]
642 [ # # ][ # # ]: 82 : if ( l == NULL || stat != CUBIT_SUCCESS )
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ - + ]
643 : 0 : return CUBIT_FALSE;
644 : : //Now l is the RTreeNode that holds the actual data (a DATA_RNODE)
645 : : //not a leaf. This was done for efficiency.
646 : 82 : RTreeNode<Y> *data_node = l;
647 [ # # ][ # # ]: 82 : l = data_node->get_parent();
[ # # ][ + - ]
648 : : //D2) [Delete record] Remove e from l.
649 : :
650 : : //remove the data node from the children and delete
651 : : //the node.
652 [ # # ][ # # ]: 82 : l->remove_child(data_node);
[ # # ][ + - ]
653 [ # # ][ # # ]: 82 : delete data_node;
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
654 : :
655 : : //D3) [Propogate Changes].
656 [ # # ][ # # ]: 82 : stat = condense_tree(l, this, new_root);
[ # # ][ + - ]
657 : : //D4) [Shorten the tree].
658 : 82 : RTreeNode<Y> *root = this;
659 [ # # ][ # # ]: 82 : if ( new_root != NULL )
[ # # ][ - + ]
660 : 0 : root = new_root;
661 [ # # ][ # # ]: 82 : if ( root->num_children() == 1 )
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ - + ]
662 : : {
663 [ # # ][ # # ]: 0 : new_root = root->get_child(0);
[ # # ][ # # ]
664 [ # # ][ # # ]: 0 : new_root->set_parent((RTreeNode<Y>*)NULL);
[ # # ][ # # ]
665 : 0 : delete_root = CUBIT_TRUE;
666 : : }
667 [ # # ][ # # ]: 82 : return CUBIT_TRUE;
[ # # ][ + - ]
668 : : }
669 : 266 : template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::find_leaf( Y e,
670 : : CubitBox &e_box,
671 : : RTreeNode<Y> *t,
672 : : RTreeNode<Y> *&l )
673 : : {
674 : : int ii;
675 : 266 : l = NULL;
676 : 266 : int loop_size = t->num_children();
677 : : RTreeNode<Y> *curr_node;
678 [ # # # # : 266 : if ( t->get_leaf_level() > LEAF_RNODE )
# # + + ]
679 : : {
680 [ # # ][ # # ]: 255 : for ( ii = 0; ii < loop_size; ii++ )
[ # # ][ + - ]
681 : : {
682 : 255 : curr_node = t->get_child(ii);
683 [ # # # # : 255 : if ( curr_node == NULL )
# # - + ]
684 : : {
685 [ # # ][ # # ]: 0 : PRINT_ERROR("Problems finding boxes in range.\n");
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
686 [ # # ][ # # ]: 0 : assert(curr_node != NULL);
[ # # ][ # # ]
687 : 0 : return CUBIT_FAILURE;
688 : : }
689 [ # # ][ # # ]: 255 : if ( e_box.overlap(GEOMETRY_RESABS, curr_node->bounding_box()) )
[ # # ][ + + ]
690 : : {
691 : : //okay now search through this now.
692 : 184 : find_leaf(e, e_box,curr_node,l);
693 [ # # # # : 184 : if ( l != NULL )
# # + + ]
694 : 82 : return CUBIT_SUCCESS;
695 : : }
696 : : }
697 : : }
698 [ # # ][ # # ]: 184 : else if ( t->is_leaf() )
[ # # ][ + - ]
699 : : {
700 : : //search through the children for e.
701 [ # # ][ # # ]: 843 : for ( ii = 0; ii < loop_size; ii++ )
[ # # ][ + + ]
702 : : {
703 : 741 : curr_node = t->get_child(ii);
704 [ # # # # : 741 : if ( curr_node == NULL )
# # - + ]
705 : : {
706 [ # # ][ # # ]: 0 : PRINT_ERROR("Problems finding boxes in range.\n");
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
707 [ # # ][ # # ]: 0 : assert(curr_node != NULL);
[ # # ][ # # ]
708 : 0 : return CUBIT_FAILURE;
709 : : }
710 [ # # ][ # # ]: 741 : if ( curr_node->get_data() == e )
[ # # ][ + + ]
711 : : {
712 : 82 : l = curr_node;
713 : 82 : return CUBIT_SUCCESS;
714 : : }
715 : : }
716 : : }
717 : 266 : return CUBIT_SUCCESS;
718 : : }
719 : 82 : template <class Y> MY_INLINE CubitBoolean RTreeNode<Y>::remove_child( RTreeNode<Y> *child )
720 : : {
721 : : //first find which item this child is at.
722 : : int ii;
723 : 82 : int index_child = -1;
724 : 82 : int loop_size = this->num_children();
725 [ # # ][ # # ]: 517 : for ( ii = 0; ii < loop_size; ii++ )
[ # # ][ + + ]
726 : : {
727 [ # # ][ # # ]: 435 : if ( myChildrenNodes[ii] == child )
[ # # ][ + + ]
728 : 82 : index_child = ii;
729 : : }
730 [ # # ][ # # ]: 82 : if ( index_child == -1 )
[ # # ][ - + ]
731 : 0 : return CUBIT_FALSE;
732 : : //Now we need to bubble the array from this point
733 : : //upward.
734 [ # # ][ # # ]: 165 : for ( ii = index_child; ii < loop_size-1; ii++ )
[ # # ][ + + ]
735 : : {
736 : 83 : myChildrenNodes[ii] = myChildrenNodes[ii+1];
737 : : }
738 : : //decrement the position of the next available child.
739 : 82 : nextChildIndex--;
740 : : //now go from nextChildIndex to the end and make sure it is
741 : : //null.
742 [ # # ][ # # ]: 385 : for (ii = nextChildIndex; ii < maxChildren; ii++ )
[ # # ][ + + ]
743 : 303 : myChildrenNodes[ii] = NULL;
744 : :
745 : 82 : return CUBIT_TRUE;
746 : : }
747 : : //--------------------------------------------------------------------------
748 : : // Algorithm: condense_tree
749 : : // Given a leaf node l from which an entry has been deleted, eliminate
750 : : // the node if it has too few entries and relocate its entries. Propagate
751 : : // node elimination upaward as necessary. Adjust all covering rectangles
752 : : // on the path to the root, making them smaller if possible.
753 : : // CT1) [Initialize] Set n=l, Set q, the set of eliminated nodes, to be
754 : : // empty.
755 : : // CT2) [Find parent entry] If n is the root, go to CT6. Otherwise
756 : : // let p be the parent of n, and let en be n's entry in p.
757 : : // CT3) [Eliminate under-full node.] If n has fewer than minChildren,
758 : : // delete en from p and add n to set q.
759 : : // CT4) [Adjust covering rectangle] If n has not been eliminated, adjust
760 : : // en's bounding box to tightly contain all entries in n.
761 : : // CT5) [Move up one level in tree] Set n=p, and repeat from CT2.
762 : : // CT6) [Reinsert orphaned entries]. Reinsert all entries of nodes in set q.
763 : : // entries from eliminated leaf nodes are re-inserted in tree leaves
764 : : // as described in algorithm insert, but entries from higher-level
765 : : // nodes must be placed higher in the tree so that leaves of their
766 : : // dependent subtrees will be on the same level as leaves of the
767 : : // main tree.
768 : : //--------------------------------------------------------------------------
769 : 82 : template <class Y> MY_INLINE CubitStatus RTreeNode<Y>::condense_tree(RTreeNode<Y> *l,
770 : : RTreeNode<Y> *root,
771 : : RTreeNode<Y> *&new_root )
772 : : {
773 : : int ii;
774 : 82 : new_root = NULL;
775 : : //CT1)
776 : 82 : RTreeNode<Y> *n = l, *p;
777 [ # # ][ # # ]: 82 : DLIList <RTreeNode<Y>*> set_q;
[ # # ][ + - ]
778 : : //CT2)
779 [ # # ][ # # ]: 164 : while ( n != root )
[ # # ][ + + ]
780 : : {
781 [ # # ][ # # ]: 82 : p = n->get_parent();
[ # # ][ + - ]
782 [ # # ][ # # ]: 82 : if ( n->num_children() < minChildren )
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ - + ]
783 : : {
784 : : //CT3
785 : : //take these children and add them to set_q.
786 [ # # ][ # # ]: 0 : for ( ii = 0;ii < n->num_children(); ii++ )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
787 [ # # ][ # # ]: 0 : set_q.append(n->get_child(ii));
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
788 : : //remove n from p.
789 [ # # ][ # # ]: 0 : p->remove_child(n);
[ # # ][ # # ]
790 : : //delete n.
791 [ # # ][ # # ]: 0 : delete n;
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
792 : : //now continue on.
793 : : }
794 : : else
795 : : {
796 : : //CT4
797 [ # # ][ # # ]: 82 : n->recalc_b_box();
[ # # ][ + - ]
798 : : }
799 : : //CT5
800 : 82 : n = p;
801 : : }
802 : : //now reinsert all nodes in set_q.
803 : : RTreeNode<Y> *curr_node, *temp_root;
804 : 82 : temp_root = root;
805 [ # # ][ # # ]: 82 : for (ii = set_q.size(); ii > 0; ii-- )
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ - + ]
806 : : {
807 [ # # ][ # # ]: 0 : curr_node = set_q.get_and_step();
[ # # ][ # # ]
808 [ # # ][ # # ]: 0 : temp_root->insert(curr_node, new_root);
[ # # ][ # # ]
809 [ # # ][ # # ]: 0 : if ( new_root != NULL )
[ # # ][ # # ]
810 : 0 : temp_root = new_root;
811 : : }
812 [ # # ][ # # ]: 82 : if ( temp_root != root )
[ # # ][ - + ]
813 : 0 : new_root = temp_root;
814 [ # # ][ # # ]: 82 : return CUBIT_SUCCESS;
[ # # ][ + - ]
815 : : }
816 : :
817 : :
818 : :
819 : :
|
