kd_tree.h
上传用户:chinafayin
上传日期:2022-04-05
资源大小:153k
文件大小:8k
源码类别:

并行计算

开发平台:

Visual C++

  1. //----------------------------------------------------------------------
  2. // File: kd_tree.h
  3. // Programmer: Sunil Arya and David Mount
  4. // Description: Declarations for standard kd-tree routines
  5. // Last modified: 05/03/05 (Version 1.1)
  6. //----------------------------------------------------------------------
  7. // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
  8. // David Mount.  All Rights Reserved.
  9. // 
  10. // This software and related documentation is part of the Approximate
  11. // Nearest Neighbor Library (ANN).  This software is provided under
  12. // the provisions of the Lesser GNU Public License (LGPL).  See the
  13. // file ../ReadMe.txt for further information.
  14. // 
  15. // The University of Maryland (U.M.) and the authors make no
  16. // representations about the suitability or fitness of this software for
  17. // any purpose.  It is provided "as is" without express or implied
  18. // warranty.
  19. //----------------------------------------------------------------------
  20. // History:
  21. // Revision 0.1  03/04/98
  22. // Initial release
  23. // Revision 1.1  05/03/05
  24. // Added fixed radius kNN search
  25. //----------------------------------------------------------------------
  26. #ifndef ANN_kd_tree_H
  27. #define ANN_kd_tree_H
  28. #include "../ANNx.h" // all ANN includes
  29. using namespace std; // make std:: available
  30. //----------------------------------------------------------------------
  31. // Generic kd-tree node
  32. //
  33. // Nodes in kd-trees are of two types, splitting nodes which contain
  34. // splitting information (a splitting hyperplane orthogonal to one
  35. // of the coordinate axes) and leaf nodes which contain point
  36. // information (an array of points stored in a bucket).  This is
  37. // handled by making a generic class kd_node, which is essentially an
  38. // empty shell, and then deriving the leaf and splitting nodes from
  39. // this.
  40. //----------------------------------------------------------------------
  41. class ANNkd_node{ // generic kd-tree node (empty shell)
  42. public:
  43. virtual ~ANNkd_node() {} // virtual distroyer
  44. virtual void ann_search(ANNdist) = 0; // tree search
  45. virtual void ann_pri_search(ANNdist) = 0; // priority search
  46. virtual void ann_FR_search(ANNdist) = 0; // fixed-radius search
  47. virtual void getStats( // get tree statistics
  48. int dim, // dimension of space
  49. ANNkdStats &st, // statistics
  50. ANNorthRect &bnd_box) = 0; // bounding box
  51. // print node
  52. virtual void print(int level, ostream &out) = 0;
  53. virtual void dump(ostream &out) = 0; // dump node
  54. friend class ANNkd_tree; // allow kd-tree to access us
  55. };
  56. //----------------------------------------------------------------------
  57. // kd-splitting function:
  58. // kd_splitter is a pointer to a splitting routine for preprocessing.
  59. // Different splitting procedures result in different strategies
  60. // for building the tree.
  61. //----------------------------------------------------------------------
  62. typedef void (*ANNkd_splitter)( // splitting routine for kd-trees
  63. ANNpointArray pa, // point array (unaltered)
  64. ANNidxArray pidx, // point indices (permuted on return)
  65. const ANNorthRect &bnds, // bounding rectangle for cell
  66. int n, // number of points
  67. int dim, // dimension of space
  68. int &cut_dim, // cutting dimension (returned)
  69. ANNcoord &cut_val, // cutting value (returned)
  70. int &n_lo); // num of points on low side (returned)
  71. //----------------------------------------------------------------------
  72. // Leaf kd-tree node
  73. // Leaf nodes of the kd-tree store the set of points associated
  74. // with this bucket, stored as an array of point indices.  These
  75. // are indices in the array points, which resides with the
  76. // root of the kd-tree.  We also store the number of points
  77. // that reside in this bucket.
  78. //----------------------------------------------------------------------
  79. class ANNkd_leaf: public ANNkd_node // leaf node for kd-tree
  80. {
  81. int n_pts; // no. points in bucket
  82. ANNidxArray bkt; // bucket of points
  83. public:
  84. ANNkd_leaf( // constructor
  85. int n, // number of points
  86. ANNidxArray b) // bucket
  87. {
  88. n_pts = n; // number of points in bucket
  89. bkt = b; // the bucket
  90. }
  91. ~ANNkd_leaf() { } // destructor (none)
  92. virtual void getStats( // get tree statistics
  93. int dim, // dimension of space
  94. ANNkdStats &st, // statistics
  95. ANNorthRect &bnd_box); // bounding box
  96. virtual void print(int level, ostream &out);// print node
  97. virtual void dump(ostream &out); // dump node
  98. virtual void ann_search(ANNdist); // standard search
  99. virtual void ann_pri_search(ANNdist); // priority search
  100. virtual void ann_FR_search(ANNdist); // fixed-radius search
  101. };
  102. //----------------------------------------------------------------------
  103. // KD_TRIVIAL is a special pointer to an empty leaf node. Since
  104. // some splitting rules generate many (more than 50%) trivial
  105. // leaves, we use this one shared node to save space.
  106. //
  107. // The pointer is initialized to NULL, but whenever a kd-tree is
  108. // created, we allocate this node, if it has not already been
  109. // allocated. This node is *never* deallocated, so it produces
  110. // a small memory leak.
  111. //----------------------------------------------------------------------
  112. extern ANNkd_leaf *KD_TRIVIAL; // trivial (empty) leaf node
  113. //----------------------------------------------------------------------
  114. // kd-tree splitting node.
  115. // Splitting nodes contain a cutting dimension and a cutting value.
  116. // These indicate the axis-parellel plane which subdivide the
  117. // box for this node. The extent of the bounding box along the
  118. // cutting dimension is maintained (this is used to speed up point
  119. // to box distance calculations) [we do not store the entire bounding
  120. // box since this may be wasteful of space in high dimensions].
  121. // We also store pointers to the 2 children.
  122. //----------------------------------------------------------------------
  123. class ANNkd_split : public ANNkd_node // splitting node of a kd-tree
  124. {
  125. int cut_dim; // dim orthogonal to cutting plane
  126. ANNcoord cut_val; // location of cutting plane
  127. ANNcoord cd_bnds[2]; // lower and upper bounds of
  128. // rectangle along cut_dim
  129. ANNkd_ptr child[2]; // left and right children
  130. public:
  131. ANNkd_split( // constructor
  132. int cd, // cutting dimension
  133. ANNcoord cv, // cutting value
  134. ANNcoord lv, ANNcoord hv, // low and high values
  135. ANNkd_ptr lc=NULL, ANNkd_ptr hc=NULL) // children
  136. {
  137. cut_dim = cd; // cutting dimension
  138. cut_val = cv; // cutting value
  139. cd_bnds[ANN_LO] = lv; // lower bound for rectangle
  140. cd_bnds[ANN_HI] = hv; // upper bound for rectangle
  141. child[ANN_LO] = lc; // left child
  142. child[ANN_HI] = hc; // right child
  143. }
  144. ~ANNkd_split() // destructor
  145. {
  146. if (child[ANN_LO]!= NULL && child[ANN_LO]!= KD_TRIVIAL)
  147. delete child[ANN_LO];
  148. if (child[ANN_HI]!= NULL && child[ANN_HI]!= KD_TRIVIAL)
  149. delete child[ANN_HI];
  150. }
  151. virtual void getStats( // get tree statistics
  152. int dim, // dimension of space
  153. ANNkdStats &st, // statistics
  154. ANNorthRect &bnd_box); // bounding box
  155. virtual void print(int level, ostream &out);// print node
  156. virtual void dump(ostream &out); // dump node
  157. virtual void ann_search(ANNdist); // standard search
  158. virtual void ann_pri_search(ANNdist); // priority search
  159. virtual void ann_FR_search(ANNdist); // fixed-radius search
  160. };
  161. //----------------------------------------------------------------------
  162. // External entry points
  163. //----------------------------------------------------------------------
  164. ANNkd_ptr rkd_tree( // recursive construction of kd-tree
  165. ANNpointArray pa, // point array (unaltered)
  166. ANNidxArray pidx, // point indices to store in subtree
  167. int n, // number of points
  168. int dim, // dimension of space
  169. int bsp, // bucket space
  170. ANNorthRect &bnd_box, // bounding box for current node
  171. ANNkd_splitter splitter); // splitting routine
  172. #endif