source: rrlib_geometry/space_partitioning/tKDTree.h @ 21:c6c1dda3d2e0

Last change on this file since 21:c6c1dda3d2e0 was 21:c6c1dda3d2e0, checked in by Tobias Föhst <foehst@…>, 8 years ago

Some renaming and the default metric is now accessible via cDEFAULT_METRIC

File size: 10.3 KB
Line 
1//
2// You received this file as part of RRLib
3// Robotics Research Library
4//
5// Copyright (C) Finroc GbR (finroc.org)
6//
7// This program is free software; you can redistribute it and/or
8// modify it under the terms of the GNU General Public License
9// as published by the Free Software Foundation; either version 2
10// of the License, or (at your option) any later version.
11//
12// This program is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15// GNU General Public License for more details.
16//
17// You should have received a copy of the GNU General Public License
18// along with this program; if not, write to the Free Software
19// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
20//
21//----------------------------------------------------------------------
22/*!\file    tKDTree.h
23 *
24 * \author  Tobias Foehst
25 *
26 * \date    2008-11-28
27 *
28 * \brief   Contains tKDTree
29 *
30 * \b tKDTree
31 *
32 * A kd-tree is a binary search-tree which nodes split a k-dimensional
33 * search space a one of the k axis. Thus, a 2d-tree that splits always
34 * in the middle of alternating axis yields a quad-tree. Its superior
35 * flexibility comes from simplifying the dimensionality and not being
36 * restricted to using always the middle of the split axis.
37 */
38//----------------------------------------------------------------------
39#ifndef __rrlib__geometry__space_partitioning__tKDTree_h__
40#define __rrlib__geometry__space_partitioning__tKDTree_h__
41
42//----------------------------------------------------------------------
43// External includes (system with <>, local with "")
44//----------------------------------------------------------------------
45
46//----------------------------------------------------------------------
47// Internal includes with ""
48//----------------------------------------------------------------------
49#include "rrlib/geometry/tPoint.h"
50#include "rrlib/geometry/tBoundingBox.h"
51
52//----------------------------------------------------------------------
53// Debugging
54//----------------------------------------------------------------------
55
56//----------------------------------------------------------------------
57// Namespace declaration
58//----------------------------------------------------------------------
59namespace rrlib
60{
61namespace geometry
62{
63
64//----------------------------------------------------------------------
65// Forward declarations / typedefs / enums
66//----------------------------------------------------------------------
67
68//----------------------------------------------------------------------
69// Class declaration
70//----------------------------------------------------------------------
71//! The kd-tree template class
72/*!
73 * This class implements a very generic kd-tree for arbitrary dimension
74 * and input-data. Therefore, it is a template that takes the following
75 * parameters:
76 *
77 * \param Tdimension     The dimension of this tree (the \e k in kd-tree)
78 * \param T              The input data (see the following note)
79 * \param TContentType   The optional specification of the content type of the input data
80 *
81 * \note
82 * The input data \a T must behave like a container-class in the way of
83 * providing access to the relevant data for this search tree. The part
84 * of the input data that is processed within this search tree has to
85 * allow an interpretation as k-dimension coordinates in the k-dimensional
86 * search space. Therefore, \a T must implement
87 * \code
88 * const TContentType operator [] (size_t i) const;
89 * \endcode
90 * for \c i in [0, \a Tdimension).\n
91 * If \a T additionally provides \a TContentType as a public \c typedef
92 * \c T::tContentType (like rrlib::math::tVector does) the third template
93 * parameter can be omitted.
94 *
95 * This allows the usage of tKDTree like the following examples show:
96 * \code
97 * // the data to create a 2d-tree for is a list of simple 2d-float-arrays
98 * std::vector<float[2]> data;
99 * // ... fill data
100 * tKDTree<2, float[2], float> kd_tree(data);
101 * \endcode
102 * \code
103 * // the data to create a 2d-tree for is a list of simple double-pointers to 4d-arrays
104 * std::vector<double *> data;
105 * // ... fill data
106 * tKDTree<4, double *, double> kd_tree(data);
107 * \endcode
108 * \code
109 * // even more complex data structures can be used
110 * class tKDTreeExample
111 * {
112 *
113 * public:
114 *
115 *   tKDTreeExample()
116 *   {
117 *     std::vector<tData> data;
118 *     // ... fill data
119 *     tKDTree<3, tData> kd_tree(data);
120 *   }
121 *
122 * private:
123 *
124 *   struct tData
125 *   {
126 *     typedef rrlib::math::tVec3d::tContentType tContentType;
127 *
128 *     rrlib::math::tVec3d data;
129 *     int some_other_information;
130 * //    tSomeType *more_other_information;
131 *
132 *     const tContentType operator [] (size_t i) const { return data[i]; }
133 *   };
134 *
135 * };
136 * \endcode
137 */
138template <size_t Tdimension, typename TElement>
139class tKDTree
140{
141
142//----------------------------------------------------------------------
143// Public methods and typedefs
144//----------------------------------------------------------------------
145public:
146
147  typedef geometry::tPoint<Tdimension, TElement> tPoint;
148  typedef std::function < TElement(const tPoint &, const tPoint &) > tMetric;
149
150  static const tMetric cDEFAULT_METRIC;
151
152  /*!
153   * \brief An inner class of the tKDTree template for the nodes of the tree
154   *
155   * This class is used to store the structure of the tree and is public to
156   * provide an interface to the information stored in the nodes.
157   *
158   * It stores the number of points that are grouped within this node, the
159   * minimum and maximum of the points' coordinates (can be used to define
160   * an axis-aligned bounding box), the center of mass of the points rooted
161   * at this node.
162   */
163  class tNode
164  {
165
166    //----------------------------------------------------------------------
167    // Public methods and typedefs
168    //----------------------------------------------------------------------
169  public:
170
171    typedef geometry::tBoundingBox<Tdimension, TElement> tBoundingBox;
172
173    /*!
174     * \brief The ctor of tNode
175     *
176     * The tNode gets a part of a \c std::vector<tConstInputIterator>
177     * defined by \a begin and \a end to manage as points below itself. It
178     * therefore splits this list and propagates the parts to nodes it creates
179     * as its own children until only single points are left.
180     *
181     * \param points_begin   An indirect iterator to the begin of the data to manage
182     * \param points_end     An indirect iterator to the end of the data to manage
183     * \param metric         A functor that computes an appropriate metric
184     */
185    template <typename TIterator>
186    tNode(TIterator points_begin, TIterator points_end, tMetric metric);
187
188    /*!
189     * brief The dtor of tKDTreeNode
190     */
191    ~tNode();
192
193    /*!
194     * \brief Get the split-axis of this node
195     *
196     * \return The index of the axis
197     */
198    inline size_t SplitAxis() const;
199
200    /*!
201     * \brief Get the split-value of this node
202     *
203     * \return The value that defines the split point \f$s: x < s \rightarrow x\f$ can be found in the left child-node
204     */
205    inline TElement SplitValue() const;
206
207    /*!
208     * \brief Get the number of points rooted at this node
209     *
210     * \return The number of points that can be found underneath this node
211     */
212    inline size_t NumberOfPoints() const;
213
214    /*!
215     * \brief Get the classification of this node being a leaf or not
216     *
217     * \return Whether this node is a leaf (\c true) or not (\c false)
218     */
219    inline bool IsLeaf() const;
220
221    /*!
222     * \brief Get the axis-aligned bounging box of the points underneath this node
223     *
224     * \return The maximum coordinates of this node
225     */
226    inline const tBoundingBox &BoundingBox() const;
227
228    /*!
229     * \brief Get the center of mass of the points underneath this node
230     *
231     * \return The center of mass of this node
232     */
233    inline const tPoint &CenterOfMass() const;
234
235    /*!
236     * \brief Get the left child of this node in the tree
237     *
238     * \return The left child of this node
239     */
240    inline const tNode &LeftChild() const;
241
242    /*!
243     * \brief Get the right child of this node in the tree
244     *
245     * \return The right child of this node
246     */
247    inline const tNode &RightChild() const;
248
249    //----------------------------------------------------------------------
250    // Private fields and methods
251    //----------------------------------------------------------------------
252  private:
253
254    tBoundingBox bounding_box;
255
256    size_t split_axis;
257    TElement split_value;
258    tNode *left_child;
259    tNode *right_child;
260
261    size_t number_of_points;
262    tPoint center_of_mass;
263
264    size_t SelectSplitAxis(tMetric metric) const;
265  };
266
267  /*!
268   * \brief The ctor of tKDTree
269   *
270   * The tKDTree creates a tree structure for a given point-set \a points.
271   * Therefore it first generates a list of iterators to the elements in
272   * \a data to benefit from the generic and fast interface instead of
273   * reordering \a data when sorting operations have to be performed.
274   *
275   * The next step is to create the root of the tree with to complete
276   * range of input data and let the ctor of tKDTreeNode create the
277   * complete tree in a recursive fashion.
278   *
279   * \param data     The data to organize in a kd-tree
280   * \param metric   A functor that computes an appropriate metric
281   *
282   * \warning
283   * The kd-tree is a static structure and has to be rebuild after changes
284   * in the underlying data.
285   */
286  template <typename TIterator>
287  tKDTree(TIterator points_begin, TIterator points_end, tMetric metric = cDEFAULT_METRIC);
288//
289//  template <typename TIterator>
290//  tKDTree(TIterator begin, TIterator end, tMetric metric);
291
292  /*!
293   * \brief The dtor of tKDTree
294   */
295  ~tKDTree();
296
297  /*!
298   * \brief Get the root of the tree to start traversal through the structure
299   *
300   * \return The uppermost node in the tree that contains all points
301   */
302  inline const tNode &Root() const;
303
304//----------------------------------------------------------------------
305// Private fields and methods
306//----------------------------------------------------------------------
307private:
308
309  tNode *root;
310
311};
312
313
314//----------------------------------------------------------------------
315// End of namespace declaration
316//----------------------------------------------------------------------
317}
318}
319
320
321#include "rrlib/geometry/space_partitioning/tKDTree.hpp"
322
323#endif
Note: See TracBrowser for help on using the repository browser.