00001 //---------------------------------------------------------------------- 00002 // File: kd_tree.h 00003 // Programmer: Sunil Arya and David Mount 00004 // Description: Declarations for standard kd-tree routines 00005 // Last modified: 05/03/05 (Version 1.1) 00006 //---------------------------------------------------------------------- 00007 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and 00008 // David Mount. All Rights Reserved. 00009 // 00010 // This software and related documentation is part of the Approximate 00011 // Nearest Neighbor Library (ANN). This software is provided under 00012 // the provisions of the Lesser GNU Public License (LGPL). See the 00013 // file ../ReadMe.txt for further information. 00014 // 00015 // The University of Maryland (U.M.) and the authors make no 00016 // representations about the suitability or fitness of this software for 00017 // any purpose. It is provided "as is" without express or implied 00018 // warranty. 00019 //---------------------------------------------------------------------- 00020 // History: 00021 // Revision 0.1 03/04/98 00022 // Initial release 00023 // Revision 1.1 05/03/05 00024 // Added fixed radius kNN search 00025 //---------------------------------------------------------------------- 00026 00027 #ifndef ANN_kd_tree_H 00028 #define ANN_kd_tree_H 00029 00030 #include <ANN/ANNx.h> // all ANN includes 00031 00032 using namespace std; // make std:: available 00033 00034 //---------------------------------------------------------------------- 00035 // Generic kd-tree node 00036 // 00037 // Nodes in kd-trees are of two types, splitting nodes which contain 00038 // splitting information (a splitting hyperplane orthogonal to one 00039 // of the coordinate axes) and leaf nodes which contain point 00040 // information (an array of points stored in a bucket). This is 00041 // handled by making a generic class kd_node, which is essentially an 00042 // empty shell, and then deriving the leaf and splitting nodes from 00043 // this. 00044 //---------------------------------------------------------------------- 00045 00046 class ANNkd_node{ // generic kd-tree node (empty shell) 00047 public: 00048 virtual ~ANNkd_node() {} // virtual distroyer 00049 00050 virtual void ann_search(ANNdist) = 0; // tree search 00051 virtual void ann_pri_search(ANNdist) = 0; // priority search 00052 virtual void ann_FR_search(ANNdist) = 0; // fixed-radius search 00053 00054 virtual void getStats( // get tree statistics 00055 int dim, // dimension of space 00056 ANNkdStats &st, // statistics 00057 ANNorthRect &bnd_box) = 0; // bounding box 00058 // print node 00059 virtual void print(int level, ostream &out) = 0; 00060 virtual void dump(ostream &out) = 0; // dump node 00061 00062 friend class ANNkd_tree; // allow kd-tree to access us 00063 }; 00064 00065 //---------------------------------------------------------------------- 00066 // kd-splitting function: 00067 // kd_splitter is a pointer to a splitting routine for preprocessing. 00068 // Different splitting procedures result in different strategies 00069 // for building the tree. 00070 //---------------------------------------------------------------------- 00071 00072 typedef void (*ANNkd_splitter)( // splitting routine for kd-trees 00073 ANNpointArray pa, // point array (unaltered) 00074 ANNidxArray pidx, // point indices (permuted on return) 00075 const ANNorthRect &bnds, // bounding rectangle for cell 00076 int n, // number of points 00077 int dim, // dimension of space 00078 int &cut_dim, // cutting dimension (returned) 00079 ANNcoord &cut_val, // cutting value (returned) 00080 int &n_lo); // num of points on low side (returned) 00081 00082 //---------------------------------------------------------------------- 00083 // Leaf kd-tree node 00084 // Leaf nodes of the kd-tree store the set of points associated 00085 // with this bucket, stored as an array of point indices. These 00086 // are indices in the array points, which resides with the 00087 // root of the kd-tree. We also store the number of points 00088 // that reside in this bucket. 00089 //---------------------------------------------------------------------- 00090 00091 class ANNkd_leaf: public ANNkd_node // leaf node for kd-tree 00092 { 00093 int n_pts; // no. points in bucket 00094 ANNidxArray bkt; // bucket of points 00095 public: 00096 ANNkd_leaf( // constructor 00097 int n, // number of points 00098 ANNidxArray b) // bucket 00099 { 00100 n_pts = n; // number of points in bucket 00101 bkt = b; // the bucket 00102 } 00103 00104 ~ANNkd_leaf() { } // destructor (none) 00105 00106 virtual void getStats( // get tree statistics 00107 int dim, // dimension of space 00108 ANNkdStats &st, // statistics 00109 ANNorthRect &bnd_box); // bounding box 00110 virtual void print(int level, ostream &out);// print node 00111 virtual void dump(ostream &out); // dump node 00112 00113 virtual void ann_search(ANNdist); // standard search 00114 virtual void ann_pri_search(ANNdist); // priority search 00115 virtual void ann_FR_search(ANNdist); // fixed-radius search 00116 }; 00117 00118 //---------------------------------------------------------------------- 00119 // KD_TRIVIAL is a special pointer to an empty leaf node. Since 00120 // some splitting rules generate many (more than 50%) trivial 00121 // leaves, we use this one shared node to save space. 00122 // 00123 // The pointer is initialized to NULL, but whenever a kd-tree is 00124 // created, we allocate this node, if it has not already been 00125 // allocated. This node is *never* deallocated, so it produces 00126 // a small memory leak. 00127 //---------------------------------------------------------------------- 00128 00129 extern ANNkd_leaf *KD_TRIVIAL; // trivial (empty) leaf node 00130 00131 //---------------------------------------------------------------------- 00132 // kd-tree splitting node. 00133 // Splitting nodes contain a cutting dimension and a cutting value. 00134 // These indicate the axis-parellel plane which subdivide the 00135 // box for this node. The extent of the bounding box along the 00136 // cutting dimension is maintained (this is used to speed up point 00137 // to box distance calculations) [we do not store the entire bounding 00138 // box since this may be wasteful of space in high dimensions]. 00139 // We also store pointers to the 2 children. 00140 //---------------------------------------------------------------------- 00141 00142 class ANNkd_split : public ANNkd_node // splitting node of a kd-tree 00143 { 00144 int cut_dim; // dim orthogonal to cutting plane 00145 ANNcoord cut_val; // location of cutting plane 00146 ANNcoord cd_bnds[2]; // lower and upper bounds of 00147 // rectangle along cut_dim 00148 ANNkd_ptr child[2]; // left and right children 00149 public: 00150 ANNkd_split( // constructor 00151 int cd, // cutting dimension 00152 ANNcoord cv, // cutting value 00153 ANNcoord lv, ANNcoord hv, // low and high values 00154 ANNkd_ptr lc=NULL, ANNkd_ptr hc=NULL) // children 00155 { 00156 cut_dim = cd; // cutting dimension 00157 cut_val = cv; // cutting value 00158 cd_bnds[ANN_LO] = lv; // lower bound for rectangle 00159 cd_bnds[ANN_HI] = hv; // upper bound for rectangle 00160 child[ANN_LO] = lc; // left child 00161 child[ANN_HI] = hc; // right child 00162 } 00163 00164 ~ANNkd_split() // destructor 00165 { 00166 if (child[ANN_LO]!= NULL && child[ANN_LO]!= KD_TRIVIAL) 00167 delete child[ANN_LO]; 00168 if (child[ANN_HI]!= NULL && child[ANN_HI]!= KD_TRIVIAL) 00169 delete child[ANN_HI]; 00170 } 00171 00172 virtual void getStats( // get tree statistics 00173 int dim, // dimension of space 00174 ANNkdStats &st, // statistics 00175 ANNorthRect &bnd_box); // bounding box 00176 virtual void print(int level, ostream &out);// print node 00177 virtual void dump(ostream &out); // dump node 00178 00179 virtual void ann_search(ANNdist); // standard search 00180 virtual void ann_pri_search(ANNdist); // priority search 00181 virtual void ann_FR_search(ANNdist); // fixed-radius search 00182 }; 00183 00184 //---------------------------------------------------------------------- 00185 // External entry points 00186 //---------------------------------------------------------------------- 00187 00188 ANNkd_ptr rkd_tree( // recursive construction of kd-tree 00189 ANNpointArray pa, // point array (unaltered) 00190 ANNidxArray pidx, // point indices to store in subtree 00191 int n, // number of points 00192 int dim, // dimension of space 00193 int bsp, // bucket space 00194 ANNorthRect &bnd_box, // bounding box for current node 00195 ANNkd_splitter splitter); // splitting routine 00196 00197 #endif
1.6.1