cgma
RTree.hpp
Go to the documentation of this file.
00001 //---------------------------------------------------------------------------
00002 // Class Name:  RTree
00003 // Description: Rectangle tree.  A tree for multidimensional access methods.
00004 // The algorithm was taken from the following paper:
00005 //        Guttman, A., "R-Trees: A Dynamic Index Structure for
00006 //              Spatial Searching", Proceedings of the SIGMOD
00007 //              Conference, Boston, June 1984, p. 47-57.
00008 // Creation Date: 3/29/02
00009 // Owner:  David R. White
00010 //---------------------------------------------------------------------------
00011 #ifndef RTREE_HPP
00012 #define RTREE_HPP
00013 
00014 #include "CubitDefines.h"
00015 #include "GeometryDefines.h"
00016 #include "AbstractTree.hpp"
00017 
00018 class CubitBox;
00019 class CubitVector;
00020 
00021 template <class X> class DLIList;
00022 template <class Y> class RTreeNode;
00023 
00024 template <class Z> class RTree : public AbstractTree<Z>
00025 {
00026 private:
00027   double myTolerance;
00028   int maxChildren;
00029   int minChildren;
00030   RTreeNode<Z> *myRoot;
00031   CubitStatus recursive_find(RTreeNode<Z> *rect_tree,
00032                              const CubitBox &range_box,
00033                              DLIList <Z> &range_members);
00034     //- recurses down the rtree to find all all the data members
00035     //- that fall in the range of the range_box.
00036 
00037   CubitStatus recursive_find(RTreeNode<Z> *rect_tree,
00038                              const CubitVector &ray_origin,
00039                              const CubitVector &ray_direction,
00040                              DLIList <Z> &range_members);
00041     //- recurses down the rtree to find all all the data members
00042     //- that fall in the range of the ray.
00043 
00044   void to_list(DLIList <RTreeNode<Z>*> &member_list,
00045                RTreeNode<Z> *top);
00046     //- converts the tree under top to a list.  Note, top is NOT in the list
00047     //- at the end.
00048   double min_dist_sq(CubitVector &q,
00049                      CubitBox &b_box);
00050     //- Calculates the distance between a point and a box, this is
00051 //- for the nearest neighbor point search.
00052 
00053   
00054    class LessThan
00055    {
00056      public:
00057      bool operator()(const Z& x, const Z& y) const
00058        {
00059          return x->get_dist() < y->get_dist(); 
00060        }
00061      
00062    };
00063 
00064 
00065   
00066 public:
00067   RTree(double tol = GEOMETRY_RESABS);
00068   RTree(double tol, int max_c, int min_c);
00069   ~RTree();
00070     //- Constructor/Destructor
00071 
00072   CubitStatus add(Z data);
00073     //- Adds the data member to the RTree.
00074 
00075   CubitStatus find( const CubitBox &range_box, DLIList <Z> &range_members);
00076     //- searches the range tree for members that intersect this range box
00077     //- within the tolerance.
00078 
00079   CubitStatus find( const CubitVector &ray_origin, const CubitVector &ray_direction,
00080       DLIList <Z> &range_members);
00081     //- searches the range tree for members that intersect this ray
00082     //- within the tolerance.
00083 
00084   CubitBoolean remove(Z data );
00085     //- Remove the data member's entry in the rectangle tree.
00086     //- Returns CUBIT_TRUE if item removed.  FALSE if item not
00087     //- in tree.
00088 
00089   typedef double (*DistSqFunc)(CubitVector &a, Z& b);
00090   CubitStatus k_nearest_neighbor(CubitVector &q,
00091                                  int k,
00092                                  double &closest_dist,
00093                                  DLIList<Z> &nearest_neighbors,
00094                                  DistSqFunc dist_sq_point_data);
00095   
00096   void set_tol(double tol)
00097     {myTolerance = tol;}
00098   double get_tol()
00099     {return myTolerance;}
00100     //- Sets/Gets the tolerance used for the bounding box overlap test,
00101     //- which is used during the range search.
00102 
00103   static bool less_than_func(RTreeNode<Z> *&node_a,
00104                              RTreeNode<Z> *&node_b);
00105     //- Function to use with the priority queue for sorting.
00106   
00107 };
00108 
00109 #include "RTree.cpp"
00110 
00111 #endif
00112 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines