Branch data     Line data    Source code

       1                 :            : //-----------------------------------------------------------------
       2                 :            : //- Class:   KDDTreeNode
       3                 :            : //- Author:  Kevin Albrecht 
       4                 :            : //- Created: 13 May 2003
       5                 :            : //- Updated: 8 Feb 2004
       6                 :            : //-
       7                 :            : //- Description:
       8                 :            : //-   Node for 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 KDDTREENODE_HPP
      21                 :            : #define KDDTREENODE_HPP
      22                 :            : 
      23                 :            : #include "CubitDefines.h"
      24                 :            : #include "GeometryDefines.h"
      25                 :            : #include "CubitBox.hpp"
      26                 :            : 
      27                 :            : //- constants that show the direction of discrimination
      28                 :            : enum DIMENSION
      29                 :            : {
      30                 :            :   DIMX, DIMY, DIMZ
      31                 :            : };
      32                 :            : 
      33                 :            : //- constants used to determine left vs. right
      34                 :            : enum DIRECTION
      35                 :            : {
      36                 :            :   DIR_NULL, DIR_EITHER, DIR_LEFT, DIR_RIGHT
      37                 :            : };
      38                 :            : 
      39                 :            : enum DISTDATA
      40                 :            : {
      41                 :            :   DD_SAFETY, DD_LEAF
      42                 :            : };
      43                 :            : 
      44                 :            : template <class X> class DLIList;
      45                 :            : 
      46                 :            : template <class Y> class KDDTreeNode 
      47                 :            : {
      48                 :            :   private:
      49                 :            :     DIMENSION myDisc;         // dimension in which this node discriminates
      50                 :            :     double myDist;            // used for nearest neigbhor searches
      51                 :            :     DISTDATA myDistData;      // also used for nearest neigbhor searches
      52                 :            : 
      53                 :            :   public:
      54                 :            :     KDDTreeNode<Y> *parent; // parent of this node
      55                 :            :     KDDTreeNode<Y> *left;   // left subtree
      56                 :            :     KDDTreeNode<Y> *right;  // right subtree
      57                 :            :     double x, y, z;         // coordinates of center point
      58                 :            :     Y data;                 // data with bounding box centered on this node
      59                 :            :     CubitBoolean valid;     // false if this node should be deleted
      60                 :            : 
      61                 :            :     CubitBox safetyBox;   // bounding box of myData and the safetyBox's of children
      62                 :            :     CubitBox boundingBox; // bounding box of myData
      63                 :            : 
      64                 :            :     //- Constructor/Destructor
      65                 :            :     KDDTreeNode (Y aData, DIMENSION aDisc = DIMX);
      66                 :            :     ~KDDTreeNode ();
      67                 :            : 
      68                 :            :     //- Get/set the child in the direction of "dir"
      69                 :            :     KDDTreeNode<Y> *get_child (DIRECTION dir) const;
      70                 :            :     void set_child (KDDTreeNode<Y> *node, DIRECTION dir);
      71                 :            : 
      72                 :            :     //- Get/set the "myDist" value
      73                 :          0 :     double get_dist () const { return myDist; }
      74                 :          0 :     void set_dist (double dist) { myDist = dist; }
      75                 :            : 
      76                 :            :     //- Get/set the "myDistData" value
      77                 :          0 :     DISTDATA get_dist_data () const { return myDistData; }
      78                 :          0 :     void set_dist_data (DISTDATA distData) { myDistData = distData; }
      79                 :            : 
      80                 :            :     //- Get/set the discriminating dimension of this node
      81                 :            :     DIMENSION get_disc () const { return myDisc; }
      82                 :          0 :     void set_disc (DIMENSION dim) { myDisc = dim; }
      83                 :            : 
      84                 :            :     //- Get the discriminator for the depth below this node
      85                 :            :     DIMENSION next_disc () const;
      86                 :            : 
      87                 :            :     //- The KD_COMPARE function as defined by Samet
      88                 :            :     DIRECTION compare (KDDTreeNode<Y> *Q) const;
      89                 :            :     DIRECTION compare_with_equality (KDDTreeNode<Y> *Q) const;
      90                 :            : };
      91                 :            : 
      92                 :            : #include "KDDTreeNode.cpp"
      93                 :            : 
      94                 :            : #endif