Branch data Line data Source code
1 : : //---------------------------------------------------------------------------
2 : : // Class Name: RTree
3 : : // Description: Rectangle tree. A tree for multidimensional access methods.
4 : : // The algorithm was taken from the following paper:
5 : : // Guttman, A., "R-Trees: A Dynamic Index Structure for
6 : : // Spatial Searching", Proceedings of the SIGMOD
7 : : // Conference, Boston, June 1984, p. 47-57.
8 : : // Creation Date: 3/29/02
9 : : // Owner: David R. White
10 : : //---------------------------------------------------------------------------
11 : : #ifndef RTREE_HPP
12 : : #define RTREE_HPP
13 : :
14 : : #include "CubitDefines.h"
15 : : #include "GeometryDefines.h"
16 : : #include "AbstractTree.hpp"
17 : :
18 : : class CubitBox;
19 : : class CubitVector;
20 : :
21 : : template <class X> class DLIList;
22 : : template <class Y> class RTreeNode;
23 : :
24 : : template <class Z> class RTree : public AbstractTree<Z>
25 : : {
26 : : private:
27 : : double myTolerance;
28 : : int maxChildren;
29 : : int minChildren;
30 : : RTreeNode<Z> *myRoot;
31 : : CubitStatus recursive_find(RTreeNode<Z> *rect_tree,
32 : : const CubitBox &range_box,
33 : : DLIList <Z> &range_members);
34 : : //- recurses down the rtree to find all all the data members
35 : : //- that fall in the range of the range_box.
36 : :
37 : : CubitStatus recursive_find(RTreeNode<Z> *rect_tree,
38 : : const CubitVector &ray_origin,
39 : : const CubitVector &ray_direction,
40 : : DLIList <Z> &range_members);
41 : : //- recurses down the rtree to find all all the data members
42 : : //- that fall in the range of the ray.
43 : :
44 : : void to_list(DLIList <RTreeNode<Z>*> &member_list,
45 : : RTreeNode<Z> *top);
46 : : //- converts the tree under top to a list. Note, top is NOT in the list
47 : : //- at the end.
48 : : double min_dist_sq(CubitVector &q,
49 : : CubitBox &b_box);
50 : : //- Calculates the distance between a point and a box, this is
51 : : //- for the nearest neighbor point search.
52 : :
53 : :
54 : : class LessThan
55 : : {
56 : : public:
57 : : bool operator()(const Z& x, const Z& y) const
58 : : {
59 : : return x->get_dist() < y->get_dist();
60 : : }
61 : :
62 : : };
63 : :
64 : :
65 : :
66 : : public:
67 : : RTree(double tol = GEOMETRY_RESABS);
68 : : RTree(double tol, int max_c, int min_c);
69 : : ~RTree();
70 : : //- Constructor/Destructor
71 : :
72 : : CubitStatus add(Z data);
73 : : //- Adds the data member to the RTree.
74 : :
75 : : CubitStatus find( const CubitBox &range_box, DLIList <Z> &range_members);
76 : : //- searches the range tree for members that intersect this range box
77 : : //- within the tolerance.
78 : :
79 : : CubitStatus find( const CubitVector &ray_origin, const CubitVector &ray_direction,
80 : : DLIList <Z> &range_members);
81 : : //- searches the range tree for members that intersect this ray
82 : : //- within the tolerance.
83 : :
84 : : CubitBoolean remove(Z data );
85 : : //- Remove the data member's entry in the rectangle tree.
86 : : //- Returns CUBIT_TRUE if item removed. FALSE if item not
87 : : //- in tree.
88 : :
89 : : typedef double (*DistSqFunc)(CubitVector &a, Z& b);
90 : : CubitStatus k_nearest_neighbor(CubitVector &q,
91 : : int k,
92 : : double &closest_dist,
93 : : DLIList<Z> &nearest_neighbors,
94 : : DistSqFunc dist_sq_point_data);
95 : :
96 : 0 : void set_tol(double tol)
97 : 0 : {myTolerance = tol;}
98 : 0 : double get_tol()
99 : 0 : {return myTolerance;}
100 : : //- Sets/Gets the tolerance used for the bounding box overlap test,
101 : : //- which is used during the range search.
102 : :
103 : : static bool less_than_func(RTreeNode<Z> *&node_a,
104 : : RTreeNode<Z> *&node_b);
105 : : //- Function to use with the priority queue for sorting.
106 : :
107 : : };
108 : :
109 : : #include "RTree.cpp"
110 : :
111 : : #endif
112 : :
|
