cgma
RStarTreeNode.hpp
Go to the documentation of this file.
00001 
00002 // Class Name:  RStarTreeNode
00003 // Description: Node of R*Tree.
00004 // The algorithm was taken from the following paper:
00005 //        Norbert Beckmann, H. Kriegel, R. Schnieder, and B. Seegar,
00006 //              "The R*-tree: An Efficient and Robust Access Method
00007 //              for Points and Rectangles", Proceedings of ACM SIGMOD
00008 //              Int'l. Conf. on Management of Data, pp. 322-331, 1990.
00009 // Creation Date: 7/21/02
00010 // Owner:  David R. White
00012 #ifndef RSTARTREENODE_HPP
00013 #define RSTARTREENODE_HPP
00014 
00015 #include "CubitDefines.h"
00016 #include "GeometryDefines.h"
00017 #include "CubitBox.hpp"
00018 
00019 template <class X> class DLIList;
00020 const int UNSET_RSTARNODE = -1;
00021 const int DATA_RSTARNODE = 0;
00022 const int LEAF_RSTARNODE = 1;
00023 
00024 template <class Y> class RStarTreeNode 
00025 {
00026 private:
00027     //Data.
00028   IttyBit markedFlag : 1;
00032   IttyBit distIsBox : 1;
00033   int myId;
00034   
00040   RStarTreeNode<Y>** myChildrenNodes;
00041   int nextChildIndex;
00042   CubitBox *myBoundingBox;
00043   Y myData;
00044   int maxChildren, minChildren; //max/min number of children.
00045   RStarTreeNode<Y> *myParent;
00046   int myLevel;
00053   double myDist;
00057   
00058   
00059 
00060     //Functions.
00061   RStarTreeNode<Y>* choose_sub_tree( RStarTreeNode<Y> *n, RStarTreeNode<Y> *e );
00067 
00068   CubitStatus overflow_treatment( RStarTreeNode<Y>* l,
00069                                   RStarTreeNode<Y>* e,
00070                                   RStarTreeNode<Y> *&ll,
00071                                   RStarTreeNode<Y> *root,
00072                                   RStarTreeNode<Y> *&new_root,
00073                                   int *overflow_flags, int levels);
00082 
00083   CubitStatus reinsert(RStarTreeNode<Y>* l,
00084                        RStarTreeNode<Y>* e,
00085                        RStarTreeNode<Y> *root,
00086                        RStarTreeNode<Y> *&new_root,
00087                        int *overflow_flags, int levels);
00092 
00093   
00094   CubitStatus adjust_tree(RStarTreeNode<Y> *l, RStarTreeNode<Y> *ll,
00095                           RStarTreeNode<Y> *root_node,
00096                           RStarTreeNode<Y> *&new_root,
00097                           int *overflow_flags,
00098                           int levels);
00103 
00104   CubitStatus split_node( RStarTreeNode<Y> *l,
00105                           RStarTreeNode<Y> *e,
00106                           RStarTreeNode<Y> *&ll );
00114   double calc_overlap( RStarTreeNode<Y> *current,
00115                        RStarTreeNode<Y> *add_to);
00121   
00122   double calc_enlargement( RStarTreeNode<Y> *current, RStarTreeNode<Y> *add_to );
00123   double calc_enlargement( CubitBox &current,
00124                            CubitBox &add_to );
00130 
00131   CubitStatus find_leaf( Y e,
00132                          CubitBox &e_box,
00133                          RStarTreeNode<Y> *t,
00134                          RStarTreeNode<Y> *&l );
00140 
00141   CubitStatus condense_tree(RStarTreeNode<Y> *l,
00142                             RStarTreeNode<Y> *root,
00143                             RStarTreeNode<Y> *&new_root );
00150     
00151   
00152   double volume(CubitBox &box);
00156   double volume(RStarTreeNode<Y>* curr);
00160 
00161   static int sort_high_x(RStarTreeNode<Y> *&n_1,
00162                          RStarTreeNode<Y> *&n_2 );
00163   static int sort_high_y(RStarTreeNode<Y> *&n_1,
00164                          RStarTreeNode<Y> *&n_2 );
00165   static int sort_high_z(RStarTreeNode<Y> *&n_1,
00166                          RStarTreeNode<Y> *&n_2 );
00167   static int sort_low_x(RStarTreeNode<Y> *&n_1,
00168                         RStarTreeNode<Y> *&n_2);
00169   static int sort_low_y(RStarTreeNode<Y> *&n_1,
00170                         RStarTreeNode<Y> *&n_2);
00171   static int sort_low_z(RStarTreeNode<Y> *&n_1,
00172                         RStarTreeNode<Y> *&n_2);
00178 
00179   static int sort_center_distance( RStarTreeNode<Y> *&n_1,
00180                                    RStarTreeNode<Y> *&n_2 );
00186 
00187   
00188 
00189   double margin(CubitBox &bounding_box);
00194 
00195   CubitBox super_box(DLIList<RStarTreeNode<Y>*> &node_list);
00199 
00200 public:
00201   RStarTreeNode(Y data, double tol, int max_children, int min_children );
00205   RStarTreeNode(CubitBox &bounding_box, int max_children, int min_children);
00209   
00210   ~RStarTreeNode();
00212 
00213   void validate_tree(int print);
00215 
00216   CubitStatus insert(RStarTreeNode<Y> *e, RStarTreeNode<Y> *&new_root,
00217                      int *overflow_flags, int levels);
00228 
00229   void set_leaf_level(int r_type)
00230   {myLevel = r_type;}
00234   int get_leaf_level()
00235     {return myLevel;}
00239 
00240   CubitBoolean is_leaf()
00241     {return (myLevel == LEAF_RSTARNODE)? CUBIT_TRUE : CUBIT_FALSE;}
00245 
00246   CubitBoolean is_data()
00247     {return (myLevel == DATA_RSTARNODE)? CUBIT_TRUE : CUBIT_FALSE;}
00251 
00252   Y get_data()
00253     {return myData;}
00257   
00258   void add_child(RStarTreeNode<Y>* child_node, CubitBoolean recalc_b_box);
00264   
00265   CubitBoolean can_add();
00269 
00270   int space_left();
00274 
00275   int num_children()
00276     {return nextChildIndex;}
00280 
00281   RStarTreeNode<Y>* get_child(int i)
00282     {return ((i < nextChildIndex) ? myChildrenNodes[i] : (RStarTreeNode<Y>*)NULL) ;}
00283   
00284     
00285   void flush(CubitBox &new_box);
00290   
00291   void recalc_b_box();
00296   
00297   RStarTreeNode<Y> *get_parent()
00298     {return myParent;}
00299   void set_parent(RStarTreeNode<Y> *parent)
00300     {myParent = parent;}
00301 
00302   CubitBoolean remove_child(RStarTreeNode<Y> *child);
00308 
00309   CubitBoolean remove(Y e, RStarTreeNode<Y> *&new_root, CubitBoolean &delete_root);
00315 
00316   CubitBox& bounding_box()
00317     {return *myBoundingBox;}
00321 
00322   double get_dist();
00323   void set_dist(double dis);
00330 
00331   int dist_is_box();
00332   void set_dist_is_box(int val);
00338   
00339       
00340 };
00341 template <class Y> inline int RStarTreeNode<Y>::dist_is_box()
00342 {
00343   return distIsBox;
00344 }
00345 template <class Y> inline void RStarTreeNode<Y>::set_dist_is_box(int val)
00346 {
00347   if ( val )
00348     distIsBox = 1;
00349   else
00350     distIsBox = 0;
00351 }
00352 
00353 template <class Y> inline double RStarTreeNode<Y>::get_dist()
00354 {
00355   return myDist;
00356 }
00357 template <class Y> inline void RStarTreeNode<Y>::set_dist(double dist)
00358 {
00359   myDist = dist;
00360 }
00361 
00362 //Calculate the volume of the box.
00363 template <class Y> inline double RStarTreeNode<Y>::volume(CubitBox &box)
00364 {
00365   return box.x_range()*box.y_range()*box.z_range();
00366 }
00367 //Calculate the volume of the RStarTreeNode.
00368 template <class Y> inline double RStarTreeNode<Y>::volume(RStarTreeNode<Y>* curr)
00369 {
00370   CubitBox box = curr->bounding_box();
00371   return box.x_range()*box.y_range()*box.z_range();
00372 }
00373 
00374 #include "RStarTreeNode.cpp"
00375 
00376 #endif
00377 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines