Branch data     Line data    Source code

       1                 :            : //-----------------------------------------------------------------
       2                 :            : //- Class:   KDDTree
       3                 :            : //- Author:  Kevin Albrecht 
       4                 :            : //- Created: 13 May 2003
       5                 :            : //- Updated: 8 Feb 2004
       6                 :            : //-
       7                 :            : //- Description:
       8                 :            : //-   Dynamic version of the k-d tree, where k=3.
       9                 :            : //-
      10                 :            : //- References:
      11                 :            : //-
      12                 :            : //-   Hanan Samet.  Design and Analysis of Spatial Data Structures.
      13                 :            : //-      Addison-Wesley, Reading, MA, 1990.
      14                 :            : //-
      15                 :            : //-   Jon Louis Bentley. Multidimensional binary search trees used
      16                 :            : //-     for associative searching. In Communications of the ACM,
      17                 :            : //-     18(9), pages 509-517, September 1975.
      18                 :            : //-----------------------------------------------------------------
      19                 :            : 
      20                 :            : #ifndef KDDTREE_HPP
      21                 :            : #define KDDTREE_HPP
      22                 :            : 
      23                 :            : // this value is a percentage
      24                 :            : #define KDDTREE_DEFAULT_SELF_BALANCING_DELETION_TOLERANCE 0.0
      25                 :            : 
      26                 :            : #include "CubitDefines.h"
      27                 :            : #include "GeometryDefines.h"
      28                 :            : #include "KDDTreeNode.hpp"
      29                 :            : #include "PriorityQueue.hpp"
      30                 :            : #include "AbstractTree.hpp"
      31                 :            : 
      32                 :            : class CubitBox;
      33                 :            : class CubitVector;
      34                 :            : 
      35                 :            : template <class X> class DLIList;
      36                 :            : template <class Y> class KDDTreeNode;
      37                 :            : 
      38                 :            : template <class Z> class KDDTree : public AbstractTree<Z>
      39                 :            : {
      40                 :            :   private:
      41                 :            :     CubitBoolean mySelfBalancingOn;
      42                 :            :     double myTolerance;
      43                 :            :     DLIList<KDDTreeNode<Z>*> myAddList;  // nodes added but not on tree
      44                 :            :     KDDTreeNode<Z> *myDeepestLeaf;       // used by "recursiveRemove" to hold the deepest leaf node
      45                 :            :     int myMarkedNodes;                   // number of nodes marked for deletion
      46                 :            :     double myDeletionTolerance;          // the deletion tolerance (floating point percentage between 0 and 1)
      47                 :            :     CubitBoolean myRandomOn;             // randomness switch
      48                 :            : 
      49                 :            :     double min_dist_sq (CubitVector &q, CubitBox &b_box);
      50                 :            : 
      51                 :            :     //- Find the depth of the tree recursively
      52                 :            :     void recursive_find_max_height (KDDTreeNode<Z> *root, int depth, int *maxdepth);
      53                 :            : 
      54                 :            :     //- Balance the tree recursively
      55                 :            :     KDDTreeNode<Z> *recursive_balance (DIMENSION dim, int left, int right,
      56                 :            :                                       KDDTreeNode<Z>* array[], KDDTreeNode<Z>* parent);
      57                 :            : 
      58                 :            :     //- Recursively find members intersecting this range box (called by "find")
      59                 :            :     void recursive_find ( KDDTreeNode<Z> *rect_tree, const CubitBox &range_box,
      60                 :            :                           DLIList <Z> &range_members );
      61                 :            : 
      62                 :            :     //- Return a pointer to the node containing the specified data
      63                 :            :     KDDTreeNode<Z> *find_node_containing_data (KDDTreeNode<Z> *subtreeRoot, Z data);
      64                 :            : 
      65                 :            :     //- Find the node with the minimum value in the D dimension (used by
      66                 :            :     //-  "recursiveRemove")
      67                 :            :     KDDTreeNode<Z> *find_minimum_node_of_dimension (KDDTreeNode<Z> *P, DIMENSION D);
      68                 :            : 
      69                 :            :     //- Insert the node on the tree
      70                 :            :     CubitStatus insert_node (KDDTreeNode<Z>* P);
      71                 :            : 
      72                 :            :     //- Immediately put all nodes on list onto the tree
      73                 :            :     CubitStatus dump_list ();
      74                 :            : 
      75                 :            :     //- Rearrange the array around the median point
      76                 :            :     int modifind (DIMENSION dim, int left, int right, KDDTreeNode<Z>* array[]);
      77                 :            : 
      78                 :            :   public:
      79                 :            :     DLIList<KDDTreeNode<Z>*> myNodeList; // nodes on tree
      80                 :            :     KDDTreeNode<Z> *root;
      81                 :            : 
      82                 :            :     //- Constructors/Destructor
      83                 :            :     KDDTree (double tol = GEOMETRY_RESABS, CubitBoolean selfBalancingOn = CUBIT_TRUE,
      84                 :            :              double selfBalancingDeletionTolerance = KDDTREE_DEFAULT_SELF_BALANCING_DELETION_TOLERANCE,
      85                 :            :              CubitBoolean randomOn = CUBIT_FALSE);
      86                 :            :     ~KDDTree();
      87                 :            : 
      88                 :            :     //- Methods for finding the maximum height of the tree and the size
      89                 :            :     //- of the tree
      90                 :            :     int find_max_height ();
      91                 :            : 
      92                 :            :     //- Sets/gets the tolerance used for the bounding box overlap test,
      93                 :            :     //- which is used during the range search
      94                 :          0 :     void set_tol (double tol) { myTolerance = tol; }
      95                 :          0 :     double get_tol () { return myTolerance; }
      96                 :            : 
      97                 :            :     //- Add a node with the data to the list
      98                 :            :     CubitStatus add (Z data);
      99                 :            : 
     100                 :            :     //- Remove the data member's entry in the tree. Returns CUBIT_TRUE
     101                 :            :     //- if item removed, CUBIT_FALSE if item not in tree
     102                 :            :     CubitBoolean remove (Z data);
     103                 :            : 
     104                 :            :     //- Balance the tree manually
     105                 :            :     //- Note: this is also called by the find method when self-balancing is on
     106                 :            :     CubitStatus balance ();
     107                 :            : 
     108                 :            :     //- Find members intersecting this range box
     109                 :            :     CubitStatus find (const CubitBox &range_box, DLIList <Z> &range_members);
     110                 :            : 
     111                 :            :     //- Distance method used by k_nearest_neighbor
     112                 :            :     typedef double (*DistSqFunc)(CubitVector &a, Z& b);
     113                 :            : 
     114                 :            :     //- Find the k nearest neighbors
     115                 :            :     CubitStatus k_nearest_neighbor (CubitVector &q, int k, double &closest_dist,
     116                 :            :                                     DLIList<Z> &nearest_neighbors,
     117                 :            :                                     DistSqFunc dist_sq_point_data
     118                 :            :                                    );
     119                 :            : 
     120                 :            :     //- Function to use with the priority queue for sorting.
     121                 :            :     static bool less_than_func (KDDTreeNode<Z> *&node_a,
     122                 :            :                                 KDDTreeNode<Z> *&node_b);
     123                 :            : };
     124                 :            : 
     125                 :            : #include "KDDTree.cpp"
     126                 :            : 
     127                 :            : #endif