source: rrlib_geometry/space_partitioning/tKDTree.h @ 20:8f9a14fd63eb

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

Readded support for different metrics using C++11 constucts

File size: 10.1 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 geometry::tBoundingBox<Tdimension, TElement> tBoundingBox;
149  typedef std::function < TElement(const tPoint &, const tPoint &) > tMetric;
150
151  /*!
152   * \brief An inner class of the tKDTree template for the nodes of the tree
153   *
154   * This class is used to store the structure of the tree and is public to
155   * provide an interface to the information stored in the nodes.
156   *
157   * It stores the number of points that are grouped within this node, the
158   * minimum and maximum of the points' coordinates (can be used to define
159   * an axis-aligned bounding box), the center of mass of the points rooted
160   * at this node.
161   */
162  class tNode
163  {
164
165    //----------------------------------------------------------------------
166    // Public methods and typedefs
167    //----------------------------------------------------------------------
168  public:
169
170    /*!
171     * \brief The ctor of tNode
172     *
173     * The tNode gets a part of a \c std::vector<tConstInputIterator>
174     * defined by \a begin and \a end to manage as points below itself. It
175     * therefore splits this list and propagates the parts to nodes it creates
176     * as its own children until only single points are left.
177     *
178     * \param begin    An indirect iterator to the begin of the data to manage
179     * \param end      An indirect iterator to the end of the data to manage
180     * \param metric   A functor that computes an appropriate metric
181     */
182    template <typename TIterator>
183    tNode(TIterator begin, TIterator end, tMetric metric);
184
185    /*!
186     * brief The dtor of tKDTreeNode
187     */
188    ~tNode();
189
190    /*!
191     * \brief Get the split-axis of this node
192     *
193     * \return The index of the axis
194     */
195    inline size_t SplitAxis() const;
196
197    /*!
198     * \brief Get the split-value of this node
199     *
200     * \return The value that defines the split point \f$s: x < s \rightarrow x\f$ can be found in the left child-node
201     */
202    inline TElement SplitValue() const;
203
204    /*!
205     * \brief Get the number of points rooted at this node
206     *
207     * \return The number of points that can be found underneath this node
208     */
209    inline size_t NumberOfPoints() const;
210
211    /*!
212     * \brief Get the classification of this node being a leaf or not
213     *
214     * \return Whether this node is a leaf (\c true) or not (\c false)
215     */
216    inline bool IsLeaf() const;
217
218    /*!
219     * \brief Get the axis-aligned boungind box of the points underneath this node
220     *
221     * \return The maximum coordinates of this node
222     */
223    inline const tBoundingBox &BoundingBox() const;
224
225    /*!
226     * \brief Get the center of mass of the points underneath this node
227     *
228     * \return The center of mass of this node
229     */
230    inline const tPoint &CenterOfMass() const;
231
232    /*!
233     * \brief Get the left child of this node in the tree
234     *
235     * \return The left child of this node
236     */
237    inline const tNode &LeftChild() const;
238
239    /*!
240     * \brief Get the right child of this node in the tree
241     *
242     * \return The right child of this node
243     */
244    inline const tNode &RightChild() const;
245
246    //----------------------------------------------------------------------
247    // Private fields and methods
248    //----------------------------------------------------------------------
249  private:
250
251    tBoundingBox bounding_box;
252
253    size_t split_axis;
254    TElement split_value;
255    tNode *left_child;
256    tNode *right_child;
257
258    size_t number_of_points;
259    tPoint center_of_mass;
260
261    size_t SelectSplitAxis(tMetric metric) const;
262  };
263
264  /*!
265   * \brief The ctor of tKDTree
266   *
267   * The tKDTree creates a tree structure for a given point-set \a points.
268   * Therefore it first generates a list of iterators to the elements in
269   * \a data to benefit from the generic and fast interface instead of
270   * reordering \a data when sorting operations have to be performed.
271   *
272   * The next step is to create the root of the tree with to complete
273   * range of input data and let the ctor of tKDTreeNode create the
274   * complete tree in a recursive fashion.
275   *
276   * \param data     The data to organize in a kd-tree
277   * \param metric   A functor that computes an appropriate metric
278   *
279   * \warning
280   * The kd-tree is a static structure and has to be rebuild after changes
281   * in the underlying data.
282   */
283  template <typename TIterator>
284  tKDTree(TIterator begin, TIterator end);
285
286  template <typename TIterator>
287  tKDTree(TIterator begin, TIterator end, tMetric metric);
288
289  /*!
290   * \brief The dtor of tKDTree
291   */
292  ~tKDTree();
293
294  /*!
295   * \brief Get the root of the tree to start traversal through the structure
296   *
297   * \return The uppermost node in the tree that contains all points
298   */
299  inline const tNode &Root() const;
300
301//----------------------------------------------------------------------
302// Private fields and methods
303//----------------------------------------------------------------------
304private:
305
306  tNode *root;
307
308};
309
310
311//----------------------------------------------------------------------
312// End of namespace declaration
313//----------------------------------------------------------------------
314}
315}
316
317
318#include "rrlib/geometry/space_partitioning/tKDTree.hpp"
319
320#endif
Note: See TracBrowser for help on using the repository browser.