Logo  0.95.0-final
Finite Element Embedded Library and Language in C++
Feel++ Feel++ on Github Feel++ community
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
kdtree.hpp
Go to the documentation of this file.
1 /* -*- mode: c++; coding: utf-8; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; show-trailing-whitespace: t -*- vim:fenc=utf-8:ft=tcl:et:sw=4:ts=4:sts=4
2 
3  This file is part of the Feel library
4 
5  Author(s): Christophe Prud'homme <christophe.prudhomme@feelpp.org>
6  Date: 2007-06-07
7 
8  Copyright (C) 2007 Université Joseph Fourier (Grenoble I)
9 
10  This library is free software; you can redistribute it and/or
11  modify it under the terms of the GNU Lesser General Public
12  License as published by the Free Software Foundation; either
13  version 3.0 of the License, or (at your option) any later version.
14 
15  This library is distributed in the hope that it will be useful,
16  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18  Lesser General Public License for more details.
19 
20  You should have received a copy of the GNU Lesser General Public
21  License along with this library; if not, write to the Free Software
22  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 */
29 #ifndef __KDTree_H
30 #define __KDTree_H 1
31 
32 #include <vector>
33 #include <boost/tuple/tuple.hpp>
34 #include <boost/tuple/tuple_comparison.hpp>
35 #include <boost/tuple/tuple_io.hpp>
36 
37 #include <feel/feelcore/feel.hpp>
38 #include <feel/feelalg/glas.hpp>
39 
40 
41 namespace Feel
42 {
43 
44 
58 class KDTree
59 {
60 public:
61 
62 
66  struct Element;
67  struct Leaf;
68  struct Node;
69 
70  typedef ublas::vector<double> node_type;
71  //in the following template, the last size_type corresponds to the global index of node in the mesh
72  typedef boost::tuple<node_type, size_type, uint16_type, size_type> index_node_type;
73  typedef std::vector<index_node_type> points_type;
74  typedef points_type::iterator points_iterator;
75  typedef points_type::const_iterator points_const_iterator;
76 
77  //here, the double corresponds at the distance with the node that is search
78  typedef boost::tuple<node_type, size_type, uint16_type, size_type, double > index_node_search_type;
79  typedef std::vector<index_node_search_type> points_search_type;
80  typedef points_search_type::iterator points_search_iterator;
81  typedef points_search_type::const_iterator points_search_const_iterator;
82 
84 
88 
89  KDTree()
90  :
91  M_tree( 0 ),
92  M_pts(),
93  M_node_search(),
94  M_PtsNearest(),
95  M_distanceMax( INT_MAX ),
96  M_nbPtMax( 4 )
97  {}
98  KDTree( KDTree const & tree )
99  :
100  M_tree( tree.M_tree ),
101  M_pts( tree.M_pts ),
102  M_node_search( tree.M_node_search ),
103  M_PtsNearest( tree.M_PtsNearest ),
104  M_distanceMax( tree.M_distanceMax ),
105  M_nbPtMax( tree.M_nbPtMax )
106  {}
107 
108  ~KDTree()
109  {
110  // destroy the tree
111  clearTree();
112  }
113 
115 
119 
120 
122 
126 
131  {
132  return M_pts.size();
133  }
134 
138  const points_type &points() const
139  {
140  return M_pts;
141  }
142 
146  const points_search_type &pointsNearNeighbor() const
147  {
148  return M_PtsNearest;
149  }
150 
151 
152  size_type nPtMaxNearNeighbor()
153  {
154  return M_nbPtMax;
155  }
156 
157 
159 
163 
164 
166 
170 
174  void clear()
175  {
176  clearTree();
177  M_pts.clear();
178  }
179 
183  void reserve( size_type n )
184  {
185  M_pts.reserve( n );
186  }
187 
192  {
193  M_nbPtMax=n;
194  }
195 
200  size_type addPoint( node_type const& n, size_type indice_global=0 )
201  {
202  size_type i = M_pts.size();
203  addPointWithId( n,i,0,indice_global );
204  return i;
205  }
209  void addPointWithId( const node_type& n, size_type i, uint16_type comp, size_type indice_global=0 )
210  {
211  if ( M_tree )
212  clearTree();
213 
214  M_pts.push_back( boost::make_tuple( n, i, comp,indice_global ) );
215  }
220  void pointsInBox( points_type &inpts,
221  const node_type &min,
222  const node_type &max );
223 
227  void search( const node_type & node_ );
228 
232  void showResultSearch();
233 
237  void writeLatexData( std::string __nameFile = "kdtreeData.tex" );
239 
240 
241 private:
242 
246  void clearTree();
247 
251  void run_search( Element * tree, uint16_type iter );
252 
256  void update_Pts_search( const index_node_type & p );
257 
258 private:
259  Element* M_tree;
260  points_type M_pts;
261 
262  //the point which we search the nearest neighbors
263  node_type M_node_search;
264  //vector of the closest neighbors
265  points_search_type M_PtsNearest;
266  //greater distance from the vector of nearest neighbors
267  double M_distanceMax;
268  //the maximum number of neighbors points that we want to search
269  size_type M_nbPtMax;
270 
271 
272 };
273 } // Feel
274 #endif /* __KDTree_H */

Generated on Sun Oct 20 2013 08:25:00 for Feel++ by doxygen 1.8.4