|
cgma
|
#include <RStarTreeNode.hpp>
Definition at line 24 of file RStarTreeNode.hpp.
| MY_INLINE RStarTreeNode< Y >::RStarTreeNode | ( | Y | data, |
| double | tol, | ||
| int | max_children, | ||
| int | min_children | ||
| ) |
Finds the bounding box of all the nodes in the list.
Definition at line 32 of file RStarTreeNode.cpp.
{
myId = id++;
maxChildren = max_children;
minChildren = min_children;
myChildrenNodes = new RStarTreeNode<Y>* [maxChildren];
int ii;
for ( ii = 0; ii < maxChildren; ii++ )
myChildrenNodes[ii] = (RStarTreeNode<Y>*) NULL;
if ( data == NULL )
{
PRINT_ERROR("Building RTree with null data is not allowed!\n");
assert(data != NULL);
}
myData = data;
myLevel = DATA_RSTARNODE;
CubitBox temp_box = data->bounding_box();
//Check to see if any of the min/max pairs are less than the tolerance.
//make them bigger if they are...
CubitVector min = temp_box.minimum();
CubitVector max = temp_box.maximum();
if ( max.x() - min.x() < tol )
{
min.x(min.x()-.6*tol);
max.x(max.x()+.6*tol);
}
if ( max.y() - min.y() < tol )
{
min.y(min.y()-.6*tol);
max.y(max.y()+.6*tol);
}
if ( max.z() - min.z() < tol )
{
min.z(min.z()-.6*tol);
max.z(max.z()+.6*tol);
}
myBoundingBox = new CubitBox(min, max);
myParent = NULL;
nextChildIndex = 0;
markedFlag = 0;
distIsBox = 1;
myDist = CUBIT_DBL_MAX;
}
| MY_INLINE RStarTreeNode< Y >::RStarTreeNode | ( | CubitBox & | bounding_box, |
| int | max_children, | ||
| int | min_children | ||
| ) |
Constructor for data.
Definition at line 77 of file RStarTreeNode.cpp.
{
myId = id++;
maxChildren = max_children;
minChildren = min_children;
myBoundingBox = new CubitBox(bounding_box);
myChildrenNodes = new RStarTreeNode<Y>* [maxChildren];
int ii;
for ( ii = 0; ii < maxChildren; ii++ )
myChildrenNodes[ii] = (RStarTreeNode<Y>*) NULL;
myData = NULL;
myLevel = UNSET_RSTARNODE;
myParent = NULL;
nextChildIndex = 0;
markedFlag = 0;
distIsBox = 1;
myDist = CUBIT_DBL_MAX;
}
| MY_INLINE RStarTreeNode< Y >::~RStarTreeNode | ( | ) |
Constructor for typical parent node.
Definition at line 100 of file RStarTreeNode.cpp.
{
if ( myChildrenNodes )
delete [] myChildrenNodes;
if ( myBoundingBox )
delete myBoundingBox;
}
| MY_INLINE void RStarTreeNode< Y >::add_child | ( | RStarTreeNode< Y > * | child_node, |
| CubitBoolean | recalc_b_box | ||
| ) |
Determine if the RStarTreeNode is a leaf node.
Definition at line 911 of file RStarTreeNode.cpp.
{
assert(nextChildIndex < maxChildren && child_node != NULL );
myChildrenNodes[nextChildIndex] = child_node;
//update the bounding box. by uniting with child node...
if ( recalc_b_box )
{
CubitBox *old_box = myBoundingBox;
myBoundingBox = new CubitBox( *old_box |= child_node->bounding_box());
delete old_box;
}
nextChildIndex++;
child_node->set_parent(this);
}
| MY_INLINE CubitStatus RStarTreeNode< Y >::adjust_tree | ( | RStarTreeNode< Y > * | l, |
| RStarTreeNode< Y > * | ll, | ||
| RStarTreeNode< Y > * | root_node, | ||
| RStarTreeNode< Y > *& | new_root, | ||
| int * | overflow_flags, | ||
| int | levels | ||
| ) | [private] |
Sorts the elements based on their distance to the centroid of the bounding rectangle. reinserts the top p nodes back into the tree (after removing them first of course.)
Definition at line 504 of file RStarTreeNode.cpp.
{
CubitStatus stat;
//we need to move up the tree and correct things that have changed.
if ( l == root_node )
{
if ( ll == NULL )
return CUBIT_SUCCESS;
else
{
//Create a new root node and store l and ll there
CubitBox root_box = l->bounding_box();
root_box |= ll->bounding_box();
new_root = new RStarTreeNode<Y>(root_box, maxChildren, minChildren);
int new_level = l->get_leaf_level() + 1;
new_root->set_leaf_level(new_level);
new_root->add_child(l, CUBIT_TRUE);
new_root->add_child(ll, CUBIT_TRUE);
return CUBIT_SUCCESS;
}
}
else if ( l == new_root && ll == NULL )
{
return CUBIT_SUCCESS;
}
else if ( l == new_root && ll != NULL )
{
//Create a new root node and store l and ll there
CubitBox root_box = l->bounding_box();
root_box |= ll->bounding_box();
new_root = new RStarTreeNode<Y>(root_box, maxChildren, minChildren);
int new_level = l->get_leaf_level() + 1;
new_root->set_leaf_level(new_level);
new_root->add_child(l, CUBIT_TRUE);
new_root->add_child(ll, CUBIT_TRUE);
return CUBIT_SUCCESS;
}
RStarTreeNode<Y> *parent_node = l->get_parent();
RStarTreeNode<Y> *new_group = NULL;
if ( ll != NULL )
{
//We need to add ll to the parent if we can,
//and then we need to update the parent's bounding box...
if ( parent_node->can_add() )
{
parent_node->add_child(ll, CUBIT_FALSE);
//we need to recalculate the bounding box for the
//entire set since both l and ll were modified...
parent_node->recalc_b_box();
}
else
{
//Now we must split the children of the parent. l should
//already be in the chilren list of the paretn. So send
//to split node the parent_node and ll.
//parent node during this process will have its b_box recalced.
stat = overflow_treatment(parent_node, ll, new_group, root_node, new_root,
overflow_flags, levels);
if ( stat != CUBIT_SUCCESS )
{
PRINT_ERROR("Problems splitting node during insertion to RTree.\n");
return CUBIT_FAILURE;
}
}
}
else
{
//just recalulate the b_box for the parent_node.
parent_node->recalc_b_box();
}
if ( parent_node->get_parent() == NULL &&
parent_node != root_node &&
parent_node != new_root )
{
PRINT_INFO("level = %d\n", parent_node->get_leaf_level());
PRINT_INFO("levels = %d\n", levels);
PRINT_ERROR("parent_node (%d) == NULL\n", parent_node->myId);
PRINT_ERROR("And l (%d) ", l->myId);
assert(0);
}
stat = adjust_tree(parent_node, new_group, root_node, new_root,
overflow_flags, levels);
if ( stat != CUBIT_SUCCESS )
return CUBIT_FAILURE;
return CUBIT_SUCCESS;
}
| CubitBox& RStarTreeNode< Y >::bounding_box | ( | void | ) | [inline] |
Removes the data e from the tree and cleans up the tree. A new root node could be found from this. Assume the root node is calling this function...
Definition at line 316 of file RStarTreeNode.hpp.
{return *myBoundingBox;}
| MY_INLINE double RStarTreeNode< Y >::calc_enlargement | ( | RStarTreeNode< Y > * | current, |
| RStarTreeNode< Y > * | add_to | ||
| ) | [private] |
Calculates the current overlap between current's children nodes and add's to it the overlap that would occur from adding add_to to that list.
Definition at line 475 of file RStarTreeNode.cpp.
{
//The enlargement area is the volume of the box that would
//be the union of current and add_to minus the volume of the current.
CubitBox curr_box = current->bounding_box();
CubitBox add_to_box = add_to->bounding_box();
CubitBox supper = curr_box;
//Unite add_to_box to the curr_box.
supper|= add_to_box;
double area_big = volume(supper);
return area_big - volume(current);
}
| MY_INLINE double RStarTreeNode< Y >::calc_enlargement | ( | CubitBox & | current, |
| CubitBox & | add_to | ||
| ) | [private] |
Definition at line 488 of file RStarTreeNode.cpp.
| MY_INLINE double RStarTreeNode< Y >::calc_overlap | ( | RStarTreeNode< Y > * | current, |
| RStarTreeNode< Y > * | add_to | ||
| ) | [private] |
Since element e won't fit into l, split l into two groups, l and ll. For the RTree, this is where most of the variations on implementations have occured. Hopefully this is the best method for splitting. Though I have seen some optimizations or variations on this that have claimed slightly better performance for given algorithms.
Definition at line 433 of file RStarTreeNode.cpp.
{
int ii, jj;
CubitBox add_to_box = add_to->bounding_box();
double total_volume = 0.0;
//calculate the total overlap currently.
CubitBox curr_child_box, other_child_box, temp_box;
for ( ii = 0; ii < current->num_children(); ii++ )
{
curr_child_box = current->get_child(ii)->bounding_box();
for ( jj = 0; jj < current->num_children(); jj++ )
{
if ( ii == jj )
continue;
temp_box = curr_child_box;
other_child_box.reset(current->get_child(jj)->bounding_box());
temp_box &= other_child_box;
total_volume += volume(temp_box);
}
}
double prev_total = total_volume;
//add to it the overlap that would occur.
for ( ii = 0; ii < current->num_children(); ii++ )
{
curr_child_box.reset( current->get_child(ii)->bounding_box());
curr_child_box &= add_to_box;
total_volume += volume(curr_child_box);
}
//now find the overlap enlargment, total - prev_total...
return (total_volume-prev_total);
}
| MY_INLINE CubitBoolean RStarTreeNode< Y >::can_add | ( | ) |
Add the child to the myChildrenNodes' list. Adds it to the next availabel spot. Won't add if overflow will occur.
Definition at line 926 of file RStarTreeNode.cpp.
{
if (nextChildIndex >= maxChildren )
return CUBIT_FALSE;
else
return CUBIT_TRUE;
}
| MY_INLINE RStarTreeNode< Y > * RStarTreeNode< Y >::choose_sub_tree | ( | RStarTreeNode< Y > * | n, |
| RStarTreeNode< Y > * | e | ||
| ) | [private] |
used for nearest neigbhor searches...
Definition at line 354 of file RStarTreeNode.cpp.
{
//If n is a leaf node, or one level greater than e,
//we are done.
if ( n->get_leaf_level() == (e->get_leaf_level() + 1) )
return n;
//Now choose the entry f in n (children of n that is)
//If the children of n are leaf nodes, then find the entry f in n
// whose rectangle needs least overlap enalargement to include the new data
// rectangle. Resolve ties by choosing the entry whose rectangle needs least
// are enlargement, then the entry with the rectangle of smallest area.
//Else Choose the entry f in n whose rectangle needs least area enlargment to include the new
//data rectangle. Resolve ties by choosing the entry with the rectangle of smallest area.
double min_enlargement = CUBIT_DBL_MAX, curr_enlargement;
double min_overlap = CUBIT_DBL_MAX, curr_overlap;
RStarTreeNode<Y> *curr_node;
int child_index = -1;
int ii;
CubitBox bounding_box;
for(ii = 0; (ii < maxChildren) && (n->myChildrenNodes[ii] != NULL); ii++ )
{
curr_node = n->myChildrenNodes[ii];
assert(curr_node->get_parent() != NULL );
if ( curr_node->get_leaf_level() == (e->get_leaf_level() + 1) )
{
curr_overlap = calc_overlap(curr_node, e);
if ( curr_overlap <= min_overlap )
{
if ( curr_overlap == min_overlap && child_index >= 0 )
{
double curr_enl = calc_enlargement(curr_node, e);
double best_enl = calc_enlargement(n->get_child(ii), e);
if ( curr_enl > best_enl )
continue;
if ( curr_enl == best_enl )
{
//only reset if the curr_node has a smaller volume.
double curr_vol = volume(curr_node);
double old_vol = volume(n->myChildrenNodes[child_index]);
if ( old_vol < curr_vol )
continue;
}
}
child_index = ii;
min_overlap = curr_overlap;
}
}
else
{
curr_enlargement = calc_enlargement(curr_node, e);
if ( curr_enlargement <= min_enlargement )
{
if ( curr_enlargement == min_enlargement && child_index >= 0 )
{
//only reset if the curr_node has a smaller volume.
double curr_vol = volume(curr_node);
double old_vol = volume(n->myChildrenNodes[child_index]);
if ( old_vol < curr_vol )
continue;
}
child_index = ii;
min_enlargement = curr_enlargement;
}
}
}
//do error checking...
if ( child_index == -1 || child_index >= maxChildren )
return (RStarTreeNode<Y>*)NULL;
RStarTreeNode<Y> *f = n->myChildrenNodes[child_index];
//Now continue on...
curr_node = choose_sub_tree(f,e);
return curr_node;
}
| MY_INLINE CubitStatus RStarTreeNode< Y >::condense_tree | ( | RStarTreeNode< Y > * | l, |
| RStarTreeNode< Y > * | root, | ||
| RStarTreeNode< Y > *& | new_root | ||
| ) | [private] |
find the entry e in the tree t. l is the entry that contains e. (e is a data member of l). The parent of l, is the leaf node containing it.
Definition at line 1105 of file RStarTreeNode.cpp.
{
int ii;
new_root = NULL;
//CT1)
RStarTreeNode<Y> *n = l, *p;
DLIList <RStarTreeNode<Y>*> set_q;
//CT2)
while ( n != root )
{
p = n->get_parent();
if ( n->num_children() < minChildren )
{
//CT3
//take these children and add them to set_q.
for ( ii = 0;ii < n->num_children(); ii++ )
set_q.append(n->get_child(ii));
//remove n from p.
p->remove_child(n);
//delete n.
delete n;
//now continue on.
}
else
{
//CT4
n->recalc_b_box();
}
//CT5
n = p;
}
//now reinsert all nodes in set_q.
RStarTreeNode<Y> *curr_node, *temp_root;
temp_root = root;
for (ii = set_q.size(); ii > 0; ii-- )
{
curr_node = set_q.get_and_step();
temp_root->insert(curr_node, new_root);
if ( new_root != NULL )
temp_root = new_root;
}
if ( temp_root != root )
new_root = temp_root;
return CUBIT_SUCCESS;
}
| int RStarTreeNode< Y >::dist_is_box | ( | ) | [inline] |
This is used in several places to store some distance on the node. It is used in sorting and overflow treatment. Basically at times the nodes need to be sorted according to some distance measurement.
Definition at line 341 of file RStarTreeNode.hpp.
{
return distIsBox;
}
| MY_INLINE CubitStatus RStarTreeNode< Y >::find_leaf | ( | Y | e, |
| CubitBox & | e_box, | ||
| RStarTreeNode< Y > * | t, | ||
| RStarTreeNode< Y > *& | l | ||
| ) | [private] |
Calculate the enlargement required for increasing the bounding box of current so that it would encapsulate the bounding box of add_to.
Definition at line 1004 of file RStarTreeNode.cpp.
{
int ii;
CubitStatus stat;
l = NULL;
int loop_size = t->num_children();
RStarTreeNode<Y> *curr_node;
if ( t->get_leaf_level() > LEAF_RSTARNODE )
{
for ( ii = 0; ii < loop_size; ii++ )
{
curr_node = t->get_child(ii);
if ( curr_node == NULL )
{
PRINT_ERROR("Problems finding boxes in range.\n");
assert(curr_node != NULL);
return CUBIT_FAILURE;
}
if ( e_box.overlap(GEOMETRY_RESABS, curr_node->bounding_box()) )
{
//okay now search through this now.
stat = find_leaf(e, e_box,curr_node,l);
if ( l != NULL )
return CUBIT_SUCCESS;
}
}
}
else if ( t->is_leaf() )
{
//search through the children for e.
for ( ii = 0; ii < loop_size; ii++ )
{
curr_node = t->get_child(ii);
if ( curr_node == NULL )
{
PRINT_ERROR("Problems finding boxes in range.\n");
assert(curr_node != NULL);
return CUBIT_FAILURE;
}
if ( curr_node->get_data() == e )
{
l = curr_node;
return CUBIT_SUCCESS;
}
}
}
return CUBIT_SUCCESS;
}
| MY_INLINE void RStarTreeNode< Y >::flush | ( | CubitBox & | new_box | ) |
Definition at line 902 of file RStarTreeNode.cpp.
{
int ii;
nextChildIndex = 0;
for ( ii = 0; ii < maxChildren; ii++ )
myChildrenNodes[ii] = NULL;
delete myBoundingBox;
myBoundingBox = new CubitBox(new_box);
}
| RStarTreeNode<Y>* RStarTreeNode< Y >::get_child | ( | int | i | ) | [inline] |
Returns the number of children in the myChildrenNode's array.
Definition at line 281 of file RStarTreeNode.hpp.
{return ((i < nextChildIndex) ? myChildrenNodes[i] : (RStarTreeNode<Y>*)NULL) ;}
| Y RStarTreeNode< Y >::get_data | ( | ) | [inline] |
Determine if the RStarTreeNode is a leaf node.
Definition at line 252 of file RStarTreeNode.hpp.
{return myData;}
| double RStarTreeNode< Y >::get_dist | ( | ) | [inline] |
Returns the bounding box of this node.
Definition at line 353 of file RStarTreeNode.hpp.
{
return myDist;
}
| int RStarTreeNode< Y >::get_leaf_level | ( | ) | [inline] |
Set the type of level of the node.
Definition at line 234 of file RStarTreeNode.hpp.
{return myLevel;}
| RStarTreeNode<Y>* RStarTreeNode< Y >::get_parent | ( | ) | [inline] |
recalculates the bounding box for the node. (won't do it if this is a data node...
Definition at line 297 of file RStarTreeNode.hpp.
{return myParent;}
| MY_INLINE CubitStatus RStarTreeNode< Y >::insert | ( | RStarTreeNode< Y > * | e, |
| RStarTreeNode< Y > *& | new_root, | ||
| int * | overflow_flags, | ||
| int | levels | ||
| ) |
Makes sure the children point to parents...
Definition at line 142 of file RStarTreeNode.cpp.
{
int print1=0;
if ( print1 )
this->validate_tree(print1);
CubitStatus stat;
new_root = NULL;//only set this if the root node changes. Assume
//that this RStarTreeNode object is the root...
RStarTreeNode<Y> *root = this;
// I1. Invoke choose_sub_tree to select a leaf node l in which to place
//e
RStarTreeNode<Y> *l = choose_sub_tree(this, e);
assert(l->get_parent() != NULL || l == this );
//just test.
// make sure l is not null.
// make sure l is one level above e.
if ( l == NULL || l->get_leaf_level() != (e->get_leaf_level() + 1) )
{
PRINT_ERROR("Choosing leaf for inseartion into rtree failed.\n");
return CUBIT_FAILURE;
}
RStarTreeNode<Y> *ll = NULL;
//I2 a) If l has room for another entry install e.
if ( l->can_add() )
{
l->add_child(e, CUBIT_TRUE);
}
else
{
//Call the overflow.
stat = overflow_treatment(l, e, ll, root, new_root,
overflow_flags, levels);
if ( stat != CUBIT_SUCCESS )
return stat;
}
//adjust the bounding boxes and if needed
//create a new root...
assert(l->get_parent() != NULL || l == root || l == new_root );
int print = 0;
if ( new_root == NULL && print )
this->validate_tree(print);
else if ( new_root != NULL && print )
new_root->validate_tree(print);
stat = adjust_tree(l, ll, root, new_root,
overflow_flags, levels);
if ( stat!= CUBIT_SUCCESS )
return stat;
return CUBIT_SUCCESS;
}
| CubitBoolean RStarTreeNode< Y >::is_data | ( | ) | [inline] |
Determine if the RStarTreeNode is a leaf node.
Definition at line 246 of file RStarTreeNode.hpp.
{return (myLevel == DATA_RSTARNODE)? CUBIT_TRUE : CUBIT_FALSE;}
| CubitBoolean RStarTreeNode< Y >::is_leaf | ( | void | ) | [inline] |
get the level of the node.
Definition at line 240 of file RStarTreeNode.hpp.
{return (myLevel == LEAF_RSTARNODE)? CUBIT_TRUE : CUBIT_FALSE;}
| MY_INLINE double RStarTreeNode< Y >::margin | ( | CubitBox & | bounding_box | ) | [private] |
Function for sorting during the reinsert function. Returns -1 if n_1->get_dist() is > than n_2, 0 if equal, else 1.
Definition at line 879 of file RStarTreeNode.cpp.
| int RStarTreeNode< Y >::num_children | ( | ) | [inline] |
Returns the number of positions left in the myChildrenNode's list.
Definition at line 275 of file RStarTreeNode.hpp.
{return nextChildIndex;}
| MY_INLINE CubitStatus RStarTreeNode< Y >::overflow_treatment | ( | RStarTreeNode< Y > * | l, |
| RStarTreeNode< Y > * | e, | ||
| RStarTreeNode< Y > *& | ll, | ||
| RStarTreeNode< Y > * | root, | ||
| RStarTreeNode< Y > *& | new_root, | ||
| int * | overflow_flags, | ||
| int | levels | ||
| ) | [private] |
Select a leaf node in which to place a new index entry e. Recursive search the subtrees of n until n is a leaf node.
Definition at line 204 of file RStarTreeNode.cpp.
{
assert(l->get_parent() != NULL || l == root || l == new_root );
CubitStatus stat;
//Test is this level is not the root level.
if ( l->get_leaf_level() != (levels-1) && overflow_flags[l->get_leaf_level()] == 0)
{
//mark this level as having been reinserted...
overflow_flags[l->get_leaf_level()] = 1;
stat = reinsert(l,e,root,new_root,overflow_flags,levels);
if ( stat != CUBIT_SUCCESS )
return stat;
}
else
{
stat = split_node(l, e, ll);
if ( stat != CUBIT_SUCCESS )
return stat;
}
return stat;
}
| MY_INLINE void RStarTreeNode< Y >::recalc_b_box | ( | ) |
Clears out the myChildrenNodes by setting the array values to null. Resets the counters and sets the range as the new_box.
Definition at line 937 of file RStarTreeNode.cpp.
{
if(myLevel == DATA_RSTARNODE )
return;
int ii;
CubitBox temp_box;
CubitBoolean is_first = CUBIT_TRUE;
for ( ii = 0; ii < nextChildIndex; ii++ )
{
if ( is_first )
{
is_first = CUBIT_FALSE;
temp_box = myChildrenNodes[ii]->bounding_box();
}
else
temp_box |= myChildrenNodes[ii]->bounding_box();
}
delete myBoundingBox;
myBoundingBox = new CubitBox(temp_box);
return;
}
| MY_INLINE CubitStatus RStarTreeNode< Y >::reinsert | ( | RStarTreeNode< Y > * | l, |
| RStarTreeNode< Y > * | e, | ||
| RStarTreeNode< Y > * | root, | ||
| RStarTreeNode< Y > *& | new_root, | ||
| int * | overflow_flags, | ||
| int | levels | ||
| ) | [private] |
Determines if the node should be split or if nodes should be reinserted. If this is not the first time that the nodes have been overflown on this level (as determed by the overflow flags), then remove p items and reinsert them hoping to get a better box distribution. Otherwise, split the node. We spend more time reinserting and less time splitting on average so the result is a better tree at basically the same cost.
Definition at line 253 of file RStarTreeNode.cpp.
{
DLIList <RStarTreeNode<Y>*> ordered_entries;
RStarTreeNode<Y> *curr_node;
CubitBox big_bound = l->bounding_box();
big_bound |= e->bounding_box();
CubitVector center_big = big_bound.center();
CubitVector center_curr;
double dist_sq;
int ii;
for ( ii = 0; ii < maxChildren; ii++)
{
curr_node = l->myChildrenNodes[ii];
center_curr = curr_node->bounding_box().center();
dist_sq = (center_curr-center_big).length_squared();
curr_node->set_dist(dist_sq);
ordered_entries.append(curr_node);
}
center_curr = e->bounding_box().center();
dist_sq = (center_curr-center_big).length_squared();
e->set_dist(dist_sq);
ordered_entries.append(e);
ordered_entries.sort( sort_center_distance );
//Make sure the sorting worked...
if (ordered_entries.get()->get_dist() < ordered_entries.next()->get_dist())
{
PRINT_ERROR("Sorting failed in R*Tree.\n");
assert(0);
return CUBIT_FAILURE;
}
//Calculate P. The rstar tree says to use 30% of M.
//I'll round up...
double P = .3*maxChildren;
int p = (int) (P+0.5);
DLIList <RStarTreeNode<Y>*> reinsert_nodes;
for ( ii = 0; ii < p; ii++ )
{
reinsert_nodes.append(ordered_entries.get_and_step());
}
//Now reverse the reinsert nodes, inorder to reinsert
//the minimum distance ones first as the paper says
//this far outperforms the max ones.
reinsert_nodes.reverse();
//remove these nodes from l.
CubitBoolean e_reinserted = CUBIT_FALSE;
for ( ii = 0; ii < p; ii++ )
{
curr_node = reinsert_nodes.get_and_step();
//remember e wasn't part of l anyways...
if ( curr_node == e )
{
e_reinserted = CUBIT_TRUE;
continue;
}
l->remove_child(curr_node);
curr_node->set_parent(NULL);
}
//ressize the bounding box.
if ( !e_reinserted )
{
l->add_child(e, CUBIT_FALSE);
}
l->recalc_b_box();
CubitStatus stat;
RStarTreeNode<Y> *changed_root = NULL;
for ( ii = 0; ii < p; ii++ )
{
curr_node = reinsert_nodes.get_and_step();
stat = root->insert(curr_node, new_root,
overflow_flags, levels);
if ( stat != CUBIT_SUCCESS || curr_node->get_parent() == NULL)
{
PRINT_ERROR("RStarTree::reinsert insertion failed.\n");
return stat;
}
if ( new_root != NULL )
{
changed_root = new_root;
root = new_root;
}
}
//if the root was split during this, like at one of the middle nodes,
//new root would get reset to null again. Soo, luckily we saved that
//change! Reassign changed_root to new_root.
if ( changed_root != NULL )
new_root = changed_root;
return CUBIT_SUCCESS;
}
| MY_INLINE CubitBoolean RStarTreeNode< Y >::remove | ( | Y | e, |
| RStarTreeNode< Y > *& | new_root, | ||
| CubitBoolean & | delete_root | ||
| ) |
Removes the child from the myChildrenNodes array and condenses the array. decrements the number of children or increments the num positions available.
Definition at line 969 of file RStarTreeNode.cpp.
{
//D1) Find node containting record.
RStarTreeNode<Y> *l = NULL;
CubitBox my_box = e->bounding_box();
CubitStatus stat = find_leaf(e, my_box, this, l);
if ( l == NULL || stat != CUBIT_SUCCESS )
return CUBIT_FALSE;
//Now l is the RStarTreeNode that holds the actual data (a DATA_RSTARNODE)
//not a leaf. This was done for efficiency.
RStarTreeNode<Y> *data_node = l;
l = data_node->get_parent();
//D2) [Delete record] Remove e from l.
//remove the data node from the children and delete
//the node.
l->remove_child(data_node);
delete data_node;
//D3) [Propogate Changes].
stat = condense_tree(l, this, new_root);
//D4) [Shorten the tree].
RStarTreeNode<Y> *root = this;
if ( new_root != NULL )
root = new_root;
if ( root->num_children() == 1 )
{
new_root = root->get_child(0);
new_root->set_parent((RStarTreeNode<Y>*)NULL);
delete_root = CUBIT_TRUE;
}
return CUBIT_TRUE;
}
| MY_INLINE CubitBoolean RStarTreeNode< Y >::remove_child | ( | RStarTreeNode< Y > * | child | ) |
Definition at line 1055 of file RStarTreeNode.cpp.
{
//first find which item this child is at.
int ii;
int index_child = -1;
int loop_size = this->num_children();
for ( ii = 0; ii < loop_size; ii++ )
{
if ( myChildrenNodes[ii] == child )
index_child = ii;
}
if ( index_child == -1 )
return CUBIT_FALSE;
//Now we need to bubble the array from this point
//upward.
for ( ii = index_child; ii < loop_size-1; ii++ )
{
myChildrenNodes[ii] = myChildrenNodes[ii+1];
}
//decrement the position of the next available child.
nextChildIndex--;
//now go from nextChildIndex to the end and make sure it is
//null.
for (ii = nextChildIndex; ii < maxChildren; ii++ )
myChildrenNodes[ii] = NULL;
return CUBIT_TRUE;
}
| void RStarTreeNode< Y >::set_dist | ( | double | dis | ) | [inline] |
Definition at line 357 of file RStarTreeNode.hpp.
| void RStarTreeNode< Y >::set_dist_is_box | ( | int | val | ) | [inline] |
Definition at line 345 of file RStarTreeNode.hpp.
| void RStarTreeNode< Y >::set_leaf_level | ( | int | r_type | ) | [inline] |
Inserts the node e into the proper position of this. Assumeing this is the root. Sometimes the root will need to be split, so a new root may be returned. If the new_root is not null, then the new_root must take the place of this... The overflow_flow flags variable needs to be initialized to be an aray of size equal to the number of levels + 1, and initialized to have values of zero. The internal code uses this as to flag the levels as they get treated for overflow.
Definition at line 229 of file RStarTreeNode.hpp.
{myLevel = r_type;}
| void RStarTreeNode< Y >::set_parent | ( | RStarTreeNode< Y > * | parent | ) | [inline] |
Definition at line 299 of file RStarTreeNode.hpp.
{myParent = parent;}
| MY_INLINE int RStarTreeNode< Y >::sort_center_distance | ( | RStarTreeNode< Y > *& | n_1, |
| RStarTreeNode< Y > *& | n_2 | ||
| ) | [static, private] |
Functions to help sort the DLIList (thats why they are static). Returns -1 if n_1 is < than n_2 in that dimension, 0 if they are equivalent or 1.
Definition at line 237 of file RStarTreeNode.cpp.
| MY_INLINE int RStarTreeNode< Y >::sort_high_x | ( | RStarTreeNode< Y > *& | n_1, |
| RStarTreeNode< Y > *& | n_2 | ||
| ) | [static, private] |
Calculate the volume of the RStarTreeNode.
Definition at line 596 of file RStarTreeNode.cpp.
{
CubitVector n_1_high = n_1->bounding_box().maximum();
CubitVector n_2_high = n_2->bounding_box().maximum();
if ( n_1_high.x() < n_2_high.x() )
return -1;
else if ( n_1_high.x() == n_2_high.x() )
return 0;
else
return 1;
}
| MY_INLINE int RStarTreeNode< Y >::sort_high_y | ( | RStarTreeNode< Y > *& | n_1, |
| RStarTreeNode< Y > *& | n_2 | ||
| ) | [static, private] |
Definition at line 610 of file RStarTreeNode.cpp.
{
CubitVector n_1_high = n_1->bounding_box().maximum();
CubitVector n_2_high = n_2->bounding_box().maximum();
if ( n_1_high.y() < n_2_high.y() )
return -1;
else if ( n_1_high.y() == n_2_high.y() )
return 0;
else
return 1;
}
| MY_INLINE int RStarTreeNode< Y >::sort_high_z | ( | RStarTreeNode< Y > *& | n_1, |
| RStarTreeNode< Y > *& | n_2 | ||
| ) | [static, private] |
Definition at line 624 of file RStarTreeNode.cpp.
{
CubitVector n_1_high = n_1->bounding_box().maximum();
CubitVector n_2_high = n_2->bounding_box().maximum();
if ( n_1_high.z() < n_2_high.z() )
return -1;
else if ( n_1_high.z() == n_2_high.z() )
return 0;
else
return 1;
}
| MY_INLINE int RStarTreeNode< Y >::sort_low_x | ( | RStarTreeNode< Y > *& | n_1, |
| RStarTreeNode< Y > *& | n_2 | ||
| ) | [static, private] |
Definition at line 638 of file RStarTreeNode.cpp.
{
CubitVector n_1_low = n_1->bounding_box().minimum();
CubitVector n_2_low = n_2->bounding_box().minimum();
if ( n_1_low.x() < n_2_low.x() )
return -1;
else if ( n_1_low.x() == n_2_low.x() )
return 0;
else
return 1;
}
| MY_INLINE int RStarTreeNode< Y >::sort_low_y | ( | RStarTreeNode< Y > *& | n_1, |
| RStarTreeNode< Y > *& | n_2 | ||
| ) | [static, private] |
Definition at line 652 of file RStarTreeNode.cpp.
{
CubitVector n_1_low = n_1->bounding_box().minimum();
CubitVector n_2_low = n_2->bounding_box().minimum();
if ( n_1_low.y() < n_2_low.y() )
return -1;
else if ( n_1_low.y() == n_2_low.y() )
return 0;
else
return 1;
}
| MY_INLINE int RStarTreeNode< Y >::sort_low_z | ( | RStarTreeNode< Y > *& | n_1, |
| RStarTreeNode< Y > *& | n_2 | ||
| ) | [static, private] |
Definition at line 666 of file RStarTreeNode.cpp.
{
CubitVector n_1_low = n_1->bounding_box().minimum();
CubitVector n_2_low = n_2->bounding_box().minimum();
if ( n_1_low.z() < n_2_low.z() )
return -1;
else if ( n_1_low.z() == n_2_low.z() )
return 0;
else
return 1;
}
| MY_INLINE int RStarTreeNode< Y >::space_left | ( | ) |
Tests if there is any space in the myChildrenNodes' list.
Definition at line 933 of file RStarTreeNode.cpp.
{
return maxChildren - nextChildIndex;
}
| MY_INLINE CubitStatus RStarTreeNode< Y >::split_node | ( | RStarTreeNode< Y > * | l, |
| RStarTreeNode< Y > * | e, | ||
| RStarTreeNode< Y > *& | ll | ||
| ) | [private] |
Ascend from a leaf node L to the root, adjusting covering bounding boxes and propagating nodes splits as necesary.
Definition at line 702 of file RStarTreeNode.cpp.
{
int ii;
//create a new list containing all the nodes we want to split.
//create two lists.
DLIList <RStarTreeNode<Y>*> ordered_low, ordered_high;
for ( ii = 0; ii < maxChildren; ii++)
{
ordered_low.append(l->myChildrenNodes[ii]);
ordered_high.append(l->myChildrenNodes[ii]);
}
ordered_low.append(e);
ordered_high.append(e);
//the input list contains all of the nodes.
int d = maxChildren - 2*minChildren + 2;
//Now do the first step, choose the split axis.
//loop over each dimension.
double local_margin, min_margin = CUBIT_DBL_MAX;
DLIList<RStarTreeNode<Y>*> best_group_1, best_group_2;
for ( ii = 0; ii < 3; ii++ )
{
//Sort the lists according to the high and low dimension.
//Both lists are ordered lowest to highest however.
switch(ii)
{
case(0):
//this is the x dimension.
ordered_low.sort(sort_low_x);
ordered_high.sort(sort_high_x);
break;
case(1):
//this is the y dimension.
ordered_low.sort(sort_low_y);
ordered_high.sort(sort_high_y);
break;
case(2):
//this is the z dimension.
ordered_low.sort(sort_low_z);
ordered_high.sort(sort_high_z);
break;
}
//Now loop over the distributions and sum the margins for the
//different distributions. The axis where the sum of its margins
//is minimal is the correct axis.
int k;
local_margin = 0.0;
double min_overlap = CUBIT_DBL_MAX;
double min_volume = CUBIT_DBL_MAX;
DLIList<RStarTreeNode<Y>*> group_1_low, group_1_high, local_best_1;
DLIList<RStarTreeNode<Y>*> group_2_low, group_2_high, local_best_2;
//just do this so that the code can look familar with the paper.
int m = minChildren;
int M = maxChildren;
//Also determine with distribution is best among these in this axis.
//Store those groups in case this axis is optimum.
for ( k = 0; k < d; k++ )
{
//build the 4 groups...
int jj;
group_1_low.clean_out();
group_2_low.clean_out();
group_1_high.clean_out();
group_2_high.clean_out();
for ( jj = 0; jj < (m-1+k); jj++ )
{
group_1_low.append(ordered_low.next(jj));
group_1_high.append(ordered_high.next(jj));
}
for ( jj = (m-1+k); jj < (M+1); jj++ )
{
group_2_low.append(ordered_low.next(jj));
group_2_high.append(ordered_high.next(jj));
}
assert(group_1_low.size() + group_2_low.size() == M+1 );
//Okay we have the groups. Now calculate the metrics.
//First find the bounding boxes for the groups.
CubitBox group_1_low_box = super_box(group_1_low);
CubitBox group_2_low_box = super_box(group_2_low);
CubitBox group_1_high_box = super_box(group_1_high);
CubitBox group_2_high_box = super_box(group_2_high);
local_margin += margin(group_1_low_box);
local_margin += margin(group_2_low_box);
local_margin += margin(group_1_high_box);
local_margin += margin(group_2_high_box);
//Okay now that we have the margin, that is the portion of the
//code for choosing the correct axis. Now make sure if this axis
//is the right one, we find the right distribution.
double overlap_low, overlap_high;
//remember &= is the overlap or intersection and the volume calculates
//the volume of the overlap or intersection.
overlap_low = volume(group_1_low_box &= group_2_low_box);
overlap_high = volume(group_1_high_box &= group_2_high_box);
CubitBoolean use_low = (overlap_low < overlap_high)? CUBIT_TRUE : CUBIT_FALSE;
double temp_overlap = use_low ? overlap_low : overlap_high;
//Choose the best distribution based on the mininum distribution
if ( temp_overlap < min_overlap )
{
min_overlap = temp_overlap;
if ( use_low )
{
local_best_1 = group_1_low;
local_best_2 = group_2_low;
}
else
{
local_best_1 = group_1_high;
local_best_2 = group_2_high;
}
}
//break ties based on the smallest volumes.
else if ( temp_overlap == min_overlap )
{
//supposed to resolve this by choosing the one with the minimum area.
double tmp_vol;
if ( use_low ){
tmp_vol = volume(group_1_low_box);
tmp_vol += volume(group_2_low_box);
}
else {
tmp_vol = volume(group_1_high_box);
tmp_vol += volume(group_2_high_box);
}
if ( tmp_vol < min_volume )
{
min_volume = tmp_vol;
if ( use_low )
{
local_best_1 = group_1_low;
local_best_2 = group_2_low;
}
else
{
local_best_1 = group_1_high;
local_best_2 = group_2_high;
}
}
}
}
//After the margin has been sumed for the entire distributions,
//choose the axis with the min margin. Note I'm not storing the
//axis because for each distribution I'm also chosing the local
//best based on overlap. Store that local best as the overal all
//best. It only gets stored if the axis is optimum...
if ( local_margin < min_margin )
{
min_margin = local_margin;
best_group_1 = local_best_1;
best_group_2 = local_best_2;
}
}
//Okay now we have the groups. Clean out l, create ll.
l->flush(best_group_1.get()->bounding_box());
l->add_child(best_group_1.get_and_step(), CUBIT_FALSE);
l->set_leaf_level(e->get_leaf_level() + 1);
for ( ii = 1; ii < best_group_1.size(); ii++ )
l->add_child(best_group_1.get_and_step(), CUBIT_TRUE);
ll = new RStarTreeNode<Y>(best_group_2.get()->bounding_box(),
maxChildren, minChildren);
ll->add_child(best_group_2.get_and_step(), CUBIT_FALSE);
ll->set_leaf_level(l->get_leaf_level());
for ( ii = 1; ii < best_group_2.size(); ii++ )
ll->add_child(best_group_2.get_and_step(), CUBIT_TRUE);
return CUBIT_SUCCESS;
}
| MY_INLINE CubitBox RStarTreeNode< Y >::super_box | ( | DLIList< RStarTreeNode< Y > * > & | node_list | ) | [private] |
Calculates the margin of the mounding box margin = ([xmax-xmin]+[ymax-ymin]+[zmax-zmin])*2^(d-1))
Definition at line 891 of file RStarTreeNode.cpp.
{
int ii;
CubitBox bounding_box = node_list.get_and_step()->bounding_box();
for ( ii = 1; ii < node_list.size(); ii++ )
{
bounding_box |= node_list.get_and_step()->bounding_box();
}
return bounding_box;
}
| MY_INLINE void RStarTreeNode< Y >::validate_tree | ( | int | ) |
Constructor/Destructor.
Definition at line 107 of file RStarTreeNode.cpp.
{
int ii;
if (print )
{
PRINT_INFO("Parent %d: Children: ", myId);
for ( ii = 0; ii < num_children(); ii++ )
{
RStarTreeNode<Y> *curr_node = myChildrenNodes[ii];
PRINT_INFO("%d ", curr_node->myId);
}
PRINT_INFO("\n");
}
for ( ii = 0; ii < num_children(); ii++ )
{
RStarTreeNode<Y> *curr_node = myChildrenNodes[ii];
assert (curr_node->get_parent() == this );
curr_node->validate_tree(print);
}
return;
}
| double RStarTreeNode< Y >::volume | ( | CubitBox & | box | ) | [inline, private] |
Given a leaf node l from which an entry has been deleted, eliminate the node if it has too few entries and relocate its entries. Propagate node elimination upaward as necessary. Adjust all covering rectangles on the path to the root, making them smaller if possible.
Definition at line 363 of file RStarTreeNode.hpp.
| double RStarTreeNode< Y >::volume | ( | RStarTreeNode< Y > * | curr | ) | [inline, private] |
Calculate the volume of the box.
Definition at line 368 of file RStarTreeNode.hpp.
{
CubitBox box = curr->bounding_box();
return box.x_range()*box.y_range()*box.z_range();
}
IttyBit RStarTreeNode< Y >::distIsBox [private] |
Generic mark flag.
Definition at line 32 of file RStarTreeNode.hpp.
IttyBit RStarTreeNode< Y >::markedFlag [private] |
Definition at line 28 of file RStarTreeNode.hpp.
int RStarTreeNode< Y >::maxChildren [private] |
Definition at line 44 of file RStarTreeNode.hpp.
int RStarTreeNode< Y >::minChildren [private] |
Definition at line 44 of file RStarTreeNode.hpp.
CubitBox* RStarTreeNode< Y >::myBoundingBox [private] |
Definition at line 42 of file RStarTreeNode.hpp.
RStarTreeNode<Y>** RStarTreeNode< Y >::myChildrenNodes [private] |
Mark if the distance measured is to the bounding box or the real data. This is for the nearest neighbor search.
Definition at line 40 of file RStarTreeNode.hpp.
Y RStarTreeNode< Y >::myData [private] |
Definition at line 43 of file RStarTreeNode.hpp.
double RStarTreeNode< Y >::myDist [private] |
Level of node Level 0 equals data level. Level 1 equals leaf node level. Higher levels are non-leaf node levels.
Definition at line 53 of file RStarTreeNode.hpp.
int RStarTreeNode< Y >::myId [private] |
Definition at line 33 of file RStarTreeNode.hpp.
int RStarTreeNode< Y >::myLevel [private] |
Definition at line 46 of file RStarTreeNode.hpp.
RStarTreeNode<Y>* RStarTreeNode< Y >::myParent [private] |
Definition at line 45 of file RStarTreeNode.hpp.
int RStarTreeNode< Y >::nextChildIndex [private] |
Definition at line 41 of file RStarTreeNode.hpp.
1.7.6.1