cgma
KDDTree.hpp
Go to the documentation of this file.
00001 //-----------------------------------------------------------------
00002 //- Class:   KDDTree
00003 //- Author:  Kevin Albrecht 
00004 //- Created: 13 May 2003
00005 //- Updated: 8 Feb 2004
00006 //-
00007 //- Description:
00008 //-   Dynamic version of the k-d tree, where k=3.
00009 //-
00010 //- References:
00011 //-
00012 //-   Hanan Samet.  Design and Analysis of Spatial Data Structures.
00013 //-      Addison-Wesley, Reading, MA, 1990.
00014 //-
00015 //-   Jon Louis Bentley. Multidimensional binary search trees used
00016 //-     for associative searching. In Communications of the ACM,
00017 //-     18(9), pages 509-517, September 1975.
00018 //-----------------------------------------------------------------
00019 
00020 #ifndef KDDTREE_HPP
00021 #define KDDTREE_HPP
00022 
00023 // this value is a percentage
00024 #define KDDTREE_DEFAULT_SELF_BALANCING_DELETION_TOLERANCE 0.0
00025 
00026 #include "CubitDefines.h"
00027 #include "GeometryDefines.h"
00028 #include "KDDTreeNode.hpp"
00029 #include "PriorityQueue.hpp"
00030 #include "AbstractTree.hpp"
00031 
00032 class CubitBox;
00033 class CubitVector;
00034 
00035 template <class X> class DLIList;
00036 template <class Y> class KDDTreeNode;
00037 
00038 template <class Z> class KDDTree : public AbstractTree<Z>
00039 {
00040   private:
00041     CubitBoolean mySelfBalancingOn;
00042     double myTolerance;
00043     DLIList<KDDTreeNode<Z>*> myAddList;  // nodes added but not on tree
00044     KDDTreeNode<Z> *myDeepestLeaf;       // used by "recursiveRemove" to hold the deepest leaf node
00045     int myMarkedNodes;                   // number of nodes marked for deletion
00046     double myDeletionTolerance;          // the deletion tolerance (floating point percentage between 0 and 1)
00047     CubitBoolean myRandomOn;             // randomness switch
00048 
00049     double min_dist_sq (CubitVector &q, CubitBox &b_box);
00050 
00051     //- Find the depth of the tree recursively
00052     void recursive_find_max_height (KDDTreeNode<Z> *root, int depth, int *maxdepth);
00053 
00054     //- Balance the tree recursively
00055     KDDTreeNode<Z> *recursive_balance (DIMENSION dim, int left, int right,
00056                                       KDDTreeNode<Z>* array[], KDDTreeNode<Z>* parent);
00057 
00058     //- Recursively find members intersecting this range box (called by "find")
00059     void recursive_find ( KDDTreeNode<Z> *rect_tree, const CubitBox &range_box,
00060                           DLIList <Z> &range_members );
00061 
00062     //- Return a pointer to the node containing the specified data
00063     KDDTreeNode<Z> *find_node_containing_data (KDDTreeNode<Z> *subtreeRoot, Z data);
00064 
00065     //- Find the node with the minimum value in the D dimension (used by
00066     //-  "recursiveRemove")
00067     KDDTreeNode<Z> *find_minimum_node_of_dimension (KDDTreeNode<Z> *P, DIMENSION D);
00068 
00069     //- Insert the node on the tree
00070     CubitStatus insert_node (KDDTreeNode<Z>* P);
00071 
00072     //- Immediately put all nodes on list onto the tree
00073     CubitStatus dump_list ();
00074 
00075     //- Rearrange the array around the median point
00076     int modifind (DIMENSION dim, int left, int right, KDDTreeNode<Z>* array[]);
00077 
00078   public:
00079     DLIList<KDDTreeNode<Z>*> myNodeList; // nodes on tree
00080     KDDTreeNode<Z> *root;
00081 
00082     //- Constructors/Destructor
00083     KDDTree (double tol = GEOMETRY_RESABS, CubitBoolean selfBalancingOn = CUBIT_TRUE,
00084              double selfBalancingDeletionTolerance = KDDTREE_DEFAULT_SELF_BALANCING_DELETION_TOLERANCE,
00085              CubitBoolean randomOn = CUBIT_FALSE);
00086     ~KDDTree();
00087 
00088     //- Methods for finding the maximum height of the tree and the size
00089     //- of the tree
00090     int find_max_height ();
00091 
00092     //- Sets/gets the tolerance used for the bounding box overlap test,
00093     //- which is used during the range search
00094     void set_tol (double tol) { myTolerance = tol; }
00095     double get_tol () { return myTolerance; }
00096 
00097     //- Add a node with the data to the list
00098     CubitStatus add (Z data);
00099 
00100     //- Remove the data member's entry in the tree. Returns CUBIT_TRUE
00101     //- if item removed, CUBIT_FALSE if item not in tree
00102     CubitBoolean remove (Z data);
00103 
00104     //- Balance the tree manually
00105     //- Note: this is also called by the find method when self-balancing is on
00106     CubitStatus balance ();
00107 
00108     //- Find members intersecting this range box
00109     CubitStatus find (const CubitBox &range_box, DLIList <Z> &range_members);
00110 
00111     //- Distance method used by k_nearest_neighbor
00112     typedef double (*DistSqFunc)(CubitVector &a, Z& b);
00113 
00114     //- Find the k nearest neighbors
00115     CubitStatus k_nearest_neighbor (CubitVector &q, int k, double &closest_dist,
00116                                     DLIList<Z> &nearest_neighbors,
00117                                     DistSqFunc dist_sq_point_data
00118                                    );
00119 
00120     //- Function to use with the priority queue for sorting.
00121     static bool less_than_func (KDDTreeNode<Z> *&node_a,
00122                                 KDDTreeNode<Z> *&node_b);
00123 };
00124 
00125 #include "KDDTree.cpp"
00126 
00127 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines