npstat is hosted by Hepforge, IPPP Durham
NPStat  5.10.0
KDTree.hh
Go to the documentation of this file.
1 #ifndef NPSTAT_KDTREE_HH_
2 #define NPSTAT_KDTREE_HH_
3 
4 /**
5 // \file KDTree.hh
6 //
7 // \brief k-d tree template
8 //
9 // Author: I. Volobouev
10 //
11 // March 2010
12 */
13 
14 #include <stdexcept>
15 
16 #include "npstat/nm/BoxND.hh"
17 #include "npstat/nm/AbsVisitor.hh"
19 
20 namespace npstat {
21  /**
22  // Basic k-d tree template. See, for example,
23  // http://en.wikipedia.org/wiki/K-d_tree for the
24  // computational geometry ideas behind this type
25  // of space partitioning.
26  //
27  // Intended for speeding up the construction of empirical copulas
28  // or copula densities. Can also be used for "sliding window"
29  // kernel density estimation, local regression, etc.
30  //
31  // Class Point must possess operator[] which returns an object
32  // or reference to Numeric or some other type which can be
33  // automatically converted to Numeric.
34  */
35  template <class Point, typename Numeric=double>
36  class KDTree
37  {
38  public:
39  typedef Point value_type;
40  typedef Numeric coord_type;
41 
42  /**
43  // For efficiency reasons, this class will not make an internal
44  // copy of the "points" vector. This vector must not be modified
45  // after KDTree construction. Otherwise tree pointers will become
46  // invalid.
47  //
48  // The arguments "dimsToUse" (and "nDimsToUse" which is the length
49  // of the "dimsToUse" array) specify which point dimensions should
50  // be used to construct the tree.
51  */
52  KDTree(const std::vector<Point>& points,
53  const unsigned* dimsToUse, unsigned nDimsToUse);
54  ~KDTree();
55 
56  /**
57  // Return the reference to the vector of points
58  // used to construct the tree
59  */
60  inline const std::vector<Point>& inputPoints() const {return points_;}
61 
62  /** The size of the vector of points used to construct the tree */
63  inline unsigned nPoints() const {return nPoints_;}
64 
65  /** Total number of nodes (trunk and leaf) */
66  inline unsigned nNodes() const {return nodes_.size();}
67 
68  /**
69  // The tree dimensionality (less or equal to the dimensionality
70  // of points used to construct the tree)
71  */
72  inline unsigned dim() const {return dim_;}
73 
74  /** The point dimensions used for tree construction */
75  inline unsigned pointIndex(const unsigned i) const
76  {
77  if (i >= dim_) throw std::out_of_range(
78  "In npstat::KDTree::pointIndex: index out of range");
79  return indices_[i];
80  }
81 
82  /**
83  // Number of points whose coordinates are all equal to
84  // or below the corresponding coordinates of the "limit" array.
85  // The length of this array must be equal to the tree
86  // dimensionality.
87  */
88  unsigned nCdf(const Numeric* limit, unsigned limitDim) const;
89 
90  /**
91  // Number of points whose coordinates are all inside
92  // the given box (including the upper boundaries). The box
93  // dimensionality must be equal to the tree dimensionality.
94  */
95  inline unsigned nInBox(const BoxND<Numeric>& box) const
96  {return nInBox(box, standardBi_);}
97 
98  /**
99  // Number of points whose coordinates are all inside the given
100  // box with the boundary inclusion handling provided. The box
101  // dimensionality must be equal to the tree dimensionality
102  // and to the size of the boundary inclusion vector.
103  */
104  unsigned nInBox(const BoxND<Numeric>& box,
105  const std::vector<BoundaryInclusion>& bv) const;
106 
107  /**
108  // Visit all points inside the given box (including the upper
109  // boundaries). This function will not call either "clear()"
110  // or "result()" methods of the visitor object, only "process".
111  */
112  template <class Result>
114  const BoxND<Numeric>& box) const;
115  private:
116  // Disable the default constructors and
117  // the assignment operator
118  KDTree();
119  KDTree(const KDTree&);
120  KDTree& operator=(const KDTree&);
121 
122  struct KDTreeNode
123  {
124  inline KDTreeNode() : point(0), split(Numeric()), splitIndex(0),
125  nPoints(0), left(0), right(0) {}
126  const Point* point;
127  Numeric split;
128  unsigned splitIndex;
129  unsigned nPoints;
130  unsigned left;
131  unsigned right;
132  };
133 
134  unsigned pointLessOrEqual(const Point* pt, const Numeric* coord) const;
135  unsigned coordsLessOrEqual(const Numeric* c1, const Numeric* c2) const;
136  unsigned pointInBox(const Point* pt, const BoxND<Numeric>& box,
137  const std::vector<BoundaryInclusion>& bv) const;
138  bool limitsInBox(const BoxND<Numeric>& box, const Numeric* lowerLimit,
139  const Numeric* upperLimit) const;
140 
141  unsigned addNode(std::vector<const Point*>& pointers,
142  unsigned level, unsigned ibegin, unsigned iend);
143 
144  // Number of points below or equal to the given one,
145  // starting with the given inode
146  unsigned countBelow(unsigned inode, const Numeric* limit,
147  Numeric* upperLimit) const;
148 
149  // Number of points in the given box, starting with the given inode
150  unsigned countInBox(unsigned inode, const BoxND<Numeric>& box,
151  const std::vector<BoundaryInclusion>& bv,
152  Numeric* lowerLimit, Numeric* upperLimit) const;
153 
154  // Recursive point lookup for the visitor
155  template <class Result>
156  void visitorRecursion(AbsVisitor<Point,Result>& visitor,
157  unsigned inode, const BoxND<Numeric>& box,
158  Numeric* lowerLimit, Numeric* upperLimit,
159  bool knownInside) const;
160 
161  const std::vector<Point>& points_;
162  unsigned* indices_;
163  std::vector<KDTreeNode> nodes_;
164  unsigned nPoints_;
165  unsigned dim_;
166 
167  mutable std::vector<Numeric> lolim_;
168  mutable std::vector<Numeric> uplim_;
169  std::vector<BoundaryInclusion> standardBi_;
170  };
171 }
172 
173 #include "npstat/nm/KDTree.icc"
174 
175 #endif // NPSTAT_KDTREE_HH_
Interface for piecemeal processing of a data collection.
Enumeration of possible boundary inclusions for an interval.
Template to represent rectangles, boxes, and hyperboxes.
Definition: KDTree.hh:37
void visitInBox(AbsVisitor< Point, Result > &visitor, const BoxND< Numeric > &box) const
unsigned nPoints() const
Definition: KDTree.hh:63
unsigned nInBox(const BoxND< Numeric > &box) const
Definition: KDTree.hh:95
unsigned nInBox(const BoxND< Numeric > &box, const std::vector< BoundaryInclusion > &bv) const
unsigned pointIndex(const unsigned i) const
Definition: KDTree.hh:75
unsigned dim() const
Definition: KDTree.hh:72
unsigned nNodes() const
Definition: KDTree.hh:66
const std::vector< Point > & inputPoints() const
Definition: KDTree.hh:60
unsigned nCdf(const Numeric *limit, unsigned limitDim) const
KDTree(const std::vector< Point > &points, const unsigned *dimsToUse, unsigned nDimsToUse)
Definition: AbsArrayProjector.hh:14
Definition: AbsVisitor.hh:20
Definition: BoxND.hh:25