nabo/kdtree_cpu.cpp
Go to the documentation of this file.
1 /*
2 
3 Copyright (c) 2010--2011, Stephane Magnenat, ASL, ETHZ, Switzerland
4 You can contact the author at <stephane at magnenat dot net>
5 
6 All rights reserved.
7 
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are met:
10  * Redistributions of source code must retain the above copyright
11  notice, this list of conditions and the following disclaimer.
12  * Redistributions in binary form must reproduce the above copyright
13  notice, this list of conditions and the following disclaimer in the
14  documentation and/or other materials provided with the distribution.
15  * Neither the name of the <organization> nor the
16  names of its contributors may be used to endorse or promote products
17  derived from this software without specific prior written permission.
18 
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL ETH-ASL BE LIABLE FOR ANY
23 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 
30 */
31 
32 #include "nabo_private.h"
33 #include "index_heap.h"
34 #include <iostream>
35 #include <stdexcept>
36 #include <limits>
37 #include <queue>
38 #include <algorithm>
39 #include <utility>
40 #ifdef HAVE_OPENMP
41 #include <omp.h>
42 #endif
43 
49 namespace Nabo
50 {
52 
53 
54  using namespace std;
55 
57 
60  template<typename T>
62  {
63  for (T i = 0; i < 64; ++i)
64  {
65  if (v == 0)
66  return i;
67  v >>= 1;
68  }
69  return 64;
70  }
71 
73 
76  template<typename T, typename CloudType>
78  {
79  T maxVal(0);
80  size_t maxIdx(0);
81  for (int i = 0; i < v.size(); ++i)
82  {
83  if (v[i] > maxVal)
84  {
85  maxVal = v[i];
86  maxIdx = i;
87  }
88  }
89  return maxIdx;
90  }
91 
92  // OPT
93  template<typename T, typename Heap, typename CloudType>
95  {
96  T minVal(std::numeric_limits<T>::max());
97  T maxVal(std::numeric_limits<T>::lowest());
98 
99  for (BuildPointsCstIt it(first); it != last; ++it)
100  {
101  const T val(cloud.coeff(dim, *it));
102  minVal = min(val, minVal);
103  maxVal = max(val, maxVal);
104  }
105 
106  return make_pair(minVal, maxVal);
107  }
108 
109  template<typename T, typename Heap, typename CloudType>
111  {
112  const int count(last - first);
113  assert(count >= 1);
114  const unsigned pos(nodes.size());
115 
116  //cerr << count << endl;
117  if (count <= int(bucketSize))
118  {
119  const uint32_t initBucketsSize(buckets.size());
120  //cerr << "creating bucket with " << count << " values" << endl;
121  for (int i = 0; i < count; ++i)
122  {
123  const Index index(*(first+i));
124  assert(index < cloud.cols());
125  buckets.push_back(BucketEntry(&cloud.coeff(0, index), index));
126  //cerr << " " << &cloud.coeff(0, index) << ", " << index << endl;
127  }
128  //cerr << "at address " << bucketStart << endl;
129  nodes.push_back(Node(createDimChildBucketSize(dim, count),initBucketsSize));
130  return pos;
131  }
132 
133  // find the largest dimension of the box
134  const unsigned cutDim = argMax<T, CloudType>(maxValues - minValues);
135  const T idealCutVal((maxValues(cutDim) + minValues(cutDim))/2);
136 
137  // get bounds from actual points
138  const pair<T,T> minMaxVals(getBounds(first, last, cutDim));
139 
140  // correct cut following bounds
141  T cutVal;
142  if (idealCutVal < minMaxVals.first)
143  cutVal = minMaxVals.first;
144  else if (idealCutVal > minMaxVals.second)
145  cutVal = minMaxVals.second;
146  else
147  cutVal = idealCutVal;
148 
149  int l(0);
150  int r(count-1);
151  // partition points around cutVal
152  while (1)
153  {
154  while (l < count && cloud.coeff(cutDim, *(first+l)) < cutVal)
155  ++l;
156  while (r >= 0 && cloud.coeff(cutDim, *(first+r)) >= cutVal)
157  --r;
158  if (l > r)
159  break;
160  swap(*(first+l), *(first+r));
161  ++l; --r;
162  }
163  const int br1 = l; // now: points[0..br1-1] < cutVal <= points[br1..count-1]
164  r = count-1;
165  // partition points[br1..count-1] around cutVal
166  while (1)
167  {
168  while (l < count && cloud.coeff(cutDim, *(first+l)) <= cutVal)
169  ++l;
170  while (r >= br1 && cloud.coeff(cutDim, *(first+r)) > cutVal)
171  --r;
172  if (l > r)
173  break;
174  swap(*(first+l), *(first+r));
175  ++l; --r;
176  }
177  const int br2 = l; // now: points[br1..br2-1] == cutVal < points[br2..count-1]
178 
179  // find best split index
180  int leftCount;
181  if (idealCutVal < minMaxVals.first)
182  leftCount = 1;
183  else if (idealCutVal > minMaxVals.second)
184  leftCount = count-1;
185  else if (br1 > count / 2)
186  leftCount = br1;
187  else if (br2 < count / 2)
188  leftCount = br2;
189  else
190  leftCount = count / 2;
191  assert(leftCount > 0);
192  /*if (leftCount >= count)
193  {
194  cerr << "Error found in kdtree:" << endl;
195  cerr << "cloud size: " << cloud.cols() << endl;
196  cerr << "count:" << count << endl;
197  cerr << "leftCount: " << leftCount << endl;
198  cerr << "br1: " << br1 << endl;
199  cerr << "br2: " << br2 << endl;
200  cerr << "idealCutVal: " << idealCutVal << endl;
201  cerr << "cutVal: " << cutVal << endl;
202  cerr << "minMaxVals.first: " << minMaxVals.first << endl;
203  cerr << "minMaxVals.second: " << minMaxVals.second << endl;
204  }*/
205  assert(leftCount < count);
206 
207  // update bounds for left
208  Vector leftMaxValues(maxValues);
209  leftMaxValues[cutDim] = cutVal;
210  // update bounds for right
211  Vector rightMinValues(minValues);
212  rightMinValues[cutDim] = cutVal;
213 
214  // add this
215  nodes.push_back(Node(0, cutVal));
216 
217  // recurse
218  const unsigned _UNUSED leftChild = buildNodes(first, first + leftCount, minValues, leftMaxValues);
219  assert(leftChild == pos + 1);
220  const unsigned rightChild = buildNodes(first + leftCount, last, rightMinValues, maxValues);
221 
222  // write right child index and return
223  nodes[pos].dimChildBucketSize = createDimChildBucketSize(cutDim, rightChild);
224  return pos;
225  }
226 
227  template<typename T, typename Heap, typename CloudType>
228  KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt<T, Heap, CloudType>::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt(const CloudType& cloud, const Index dim, const unsigned creationOptionFlags, const Parameters& additionalParameters):
229  NearestNeighbourSearch<T, CloudType>::NearestNeighbourSearch(cloud, dim, creationOptionFlags),
230  bucketSize(additionalParameters.get<unsigned>("bucketSize", 8)),
231  dimBitCount(getStorageBitCount<uint32_t>(this->dim)),
232  dimMask((1<<dimBitCount)-1)
233  {
234  if (bucketSize < 2)
235  throw runtime_error("Requested bucket size " + std::to_string(bucketSize) + ", but must be larger than 2");
236  if (cloud.cols() <= bucketSize)
237  {
238  // make a single-bucket tree
239  for (int i = 0; i < cloud.cols(); ++i)
240  buckets.push_back(BucketEntry(&cloud.coeff(0, i), i));
241  nodes.push_back(Node(createDimChildBucketSize(this->dim, cloud.cols()),uint32_t(0)));
242  return;
243  }
244 
245  const uint64_t maxNodeCount((0x1ULL << (32-dimBitCount)) - 1);
246  const uint64_t estimatedNodeCount(cloud.cols() / (bucketSize / 2));
247  if (estimatedNodeCount > maxNodeCount)
248  {
249  throw runtime_error("Cloud has a risk to have more nodes (" + std::to_string(estimatedNodeCount) + ") than the kd-tree allows (" + std::to_string(maxNodeCount) + "). "
250  "The kd-tree has " + std::to_string(dimBitCount) + " bits for dimensions and " + std::to_string((32-dimBitCount)) + " bits for node indices");
251  }
252 
253  // build point vector and compute bounds
254  BuildPoints buildPoints;
255  buildPoints.reserve(cloud.cols());
256  for (int i = 0; i < cloud.cols(); ++i)
257  {
258  const Vector& v(cloud.block(0,i,this->dim,1));
259  buildPoints.push_back(i);
260 #ifdef EIGEN3_API
261  const_cast<Vector&>(minBound) = minBound.array().min(v.array());
262  const_cast<Vector&>(maxBound) = maxBound.array().max(v.array());
263 #else // EIGEN3_API
264  const_cast<Vector&>(minBound) = minBound.cwise().min(v);
265  const_cast<Vector&>(maxBound) = maxBound.cwise().max(v);
266 #endif // EIGEN3_API
267  }
268 
269  // create nodes
270  buildNodes(buildPoints.begin(), buildPoints.end(), minBound, maxBound);
271  buildPoints.clear();
272  }
273 
274  template<typename T, typename Heap, typename CloudType>
275  unsigned long KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt<T, Heap, CloudType>::knn(const Matrix& query, IndexMatrix& indices, Matrix& dists2, const Index k, const T epsilon, const unsigned optionFlags, const T maxRadius) const
276  {
277  checkSizesKnn(query, indices, dists2, k, optionFlags);
278 
279  const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T>::ALLOW_SELF_MATCH);
280  const bool sortResults(optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS);
281  const bool collectStatistics(creationOptionFlags & NearestNeighbourSearch<T>::TOUCH_STATISTICS);
282  const T maxRadius2(maxRadius * maxRadius);
283  const T maxError2((1+epsilon)*(1+epsilon));
284  const int colCount(query.cols());
285 
286  assert(nodes.size() > 0);
287 
288  IndexMatrix result(k, query.cols());
289  unsigned long leafTouchedCount(0);
290 
291 #pragma omp parallel
292  {
293 
294  Heap heap(k);
295  std::vector<T> off(dim, 0);
296 
297 #pragma omp for reduction(+:leafTouchedCount) schedule(guided,32)
298  for (int i = 0; i < colCount; ++i)
299  {
300  leafTouchedCount += onePointKnn(query, indices, dists2, i, heap, off, maxError2, maxRadius2, allowSelfMatch, collectStatistics, sortResults);
301  }
302  }
303  return leafTouchedCount;
304  }
305 
306  template<typename T, typename Heap, typename CloudType>
307  unsigned long KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt<T, Heap, CloudType>::knn(const Matrix& query, IndexMatrix& indices, Matrix& dists2, const Vector& maxRadii, const Index k, const T epsilon, const unsigned optionFlags) const
308  {
309  checkSizesKnn(query, indices, dists2, k, optionFlags, &maxRadii);
310 
311  const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T>::ALLOW_SELF_MATCH);
312  const bool sortResults(optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS);
313  const bool collectStatistics(creationOptionFlags & NearestNeighbourSearch<T>::TOUCH_STATISTICS);
314  const T maxError2((1+epsilon)*(1+epsilon));
315  const int colCount(query.cols());
316 
317  assert(nodes.size() > 0);
318  IndexMatrix result(k, query.cols());
319  unsigned long leafTouchedCount(0);
320 
321 #pragma omp parallel
322  {
323 
324  Heap heap(k);
325  std::vector<T> off(dim, 0);
326 
327 #pragma omp for reduction(+:leafTouchedCount) schedule(guided,32)
328  for (int i = 0; i < colCount; ++i)
329  {
330  const T maxRadius(maxRadii[i]);
331  const T maxRadius2(maxRadius * maxRadius);
332  leafTouchedCount += onePointKnn(query, indices, dists2, i, heap, off, maxError2, maxRadius2, allowSelfMatch, collectStatistics, sortResults);
333  }
334  }
335  return leafTouchedCount;
336  }
337 
338  template<typename T, typename Heap, typename CloudType>
339  unsigned long KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt<T, Heap, CloudType>::onePointKnn(const Matrix& query, IndexMatrix& indices, Matrix& dists2, int i, Heap& heap, std::vector<T>& off, const T maxError2, const T maxRadius2, const bool allowSelfMatch, const bool collectStatistics, const bool sortResults) const
340  {
341  fill(off.begin(), off.end(), static_cast<T>(0));
342  heap.reset();
343  unsigned long leafTouchedCount(0);
344 
345  if (allowSelfMatch)
346  {
347  if (collectStatistics)
348  leafTouchedCount += recurseKnn<true, true>(&query.coeff(0, i), 0, 0, heap, off, maxError2, maxRadius2);
349  else
350  recurseKnn<true, false>(&query.coeff(0, i), 0, 0, heap, off, maxError2, maxRadius2);
351  }
352  else
353  {
354  if (collectStatistics)
355  leafTouchedCount += recurseKnn<false, true>(&query.coeff(0, i), 0, 0, heap, off, maxError2, maxRadius2);
356  else
357  recurseKnn<false, false>(&query.coeff(0, i), 0, 0, heap, off, maxError2, maxRadius2);
358  }
359 
360  if (sortResults)
361  heap.sort();
362 
363  heap.getData(indices.col(i), dists2.col(i));
364  return leafTouchedCount;
365  }
366 
367  template<typename T, typename Heap, typename CloudType> template<bool allowSelfMatch, bool collectStatistics>
368  unsigned long KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt<T, Heap, CloudType>::recurseKnn(const T* query, const unsigned n, T rd, Heap& heap, std::vector<T>& off, const T maxError2, const T maxRadius2) const
369  {
370  const Node& node(nodes[n]);
371  const uint32_t cd(getDim(node.dimChildBucketSize));
372 
373  if (cd == uint32_t(dim))
374  {
375  //cerr << "entering bucket " << node.bucket << endl;
376  const BucketEntry* bucket(&buckets[node.bucketIndex]);
377  const uint32_t bucketSize(getChildBucketSize(node.dimChildBucketSize));
378  for (uint32_t i = 0; i < bucketSize; ++i)
379  {
380  //cerr << " " << bucket-> pt << endl;
381  //const T dist(dist2<T>(query, cloud.col(index)));
382  //const T dist((query - cloud.col(index)).squaredNorm());
383  T dist(0);
384  const T* qPtr(query);
385  const T* dPtr(bucket->pt);
386  for (int i = 0; i < this->dim; ++i)
387  {
388  const T diff(*qPtr - *dPtr);
389  dist += diff*diff;
390  qPtr++; dPtr++;
391  }
392  if ((dist <= maxRadius2) &&
393  (dist < heap.headValue()) &&
394  (allowSelfMatch || (dist > numeric_limits<T>::epsilon()))
395  )
396  heap.replaceHead(bucket->index, dist);
397  ++bucket;
398  }
399  return (unsigned long)(bucketSize);
400  }
401  else
402  {
403  const unsigned rightChild(getChildBucketSize(node.dimChildBucketSize));
404  unsigned long leafVisitedCount(0);
405  T& offcd(off[cd]);
406  //const T old_off(off.coeff(cd));
407  const T old_off(offcd);
408  const T new_off(query[cd] - node.cutVal);
409  if (new_off > 0)
410  {
411  if (collectStatistics)
412  leafVisitedCount += recurseKnn<allowSelfMatch, true>(query, rightChild, rd, heap, off, maxError2, maxRadius2);
413  else
414  recurseKnn<allowSelfMatch, false>(query, rightChild, rd, heap, off, maxError2, maxRadius2);
415  rd += - old_off*old_off + new_off*new_off;
416  if ((rd <= maxRadius2) &&
417  (rd * maxError2 < heap.headValue()))
418  {
419  offcd = new_off;
420  if (collectStatistics)
421  leafVisitedCount += recurseKnn<allowSelfMatch, true>(query, n + 1, rd, heap, off, maxError2, maxRadius2);
422  else
423  recurseKnn<allowSelfMatch, false>(query, n + 1, rd, heap, off, maxError2, maxRadius2);
424  offcd = old_off;
425  }
426  }
427  else
428  {
429  if (collectStatistics)
430  leafVisitedCount += recurseKnn<allowSelfMatch, true>(query, n+1, rd, heap, off, maxError2, maxRadius2);
431  else
432  recurseKnn<allowSelfMatch, false>(query, n+1, rd, heap, off, maxError2, maxRadius2);
433  rd += - old_off*old_off + new_off*new_off;
434  if ((rd <= maxRadius2) &&
435  (rd * maxError2 < heap.headValue()))
436  {
437  offcd = new_off;
438  if (collectStatistics)
439  leafVisitedCount += recurseKnn<allowSelfMatch, true>(query, rightChild, rd, heap, off, maxError2, maxRadius2);
440  else
441  recurseKnn<allowSelfMatch, false>(query, rightChild, rd, heap, off, maxError2, maxRadius2);
442  offcd = old_off;
443  }
444  }
445  return leafVisitedCount;
446  }
447  }
448 
453 
458 
459  template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt<float,IndexHeapSTL<int,float>,Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
460  template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt<float,IndexHeapBruteForceVector<int,float>,Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
461  template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt<double,IndexHeapSTL<int,double>,Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
462  template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt<double,IndexHeapBruteForceVector<int,double>,Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
463 
465 }
466 /* vim: set ts=8 sw=8 tw=0 noexpandtab cindent softtabstop=8 :*/
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BuildPointsCstIt
BuildPoints::const_iterator BuildPointsCstIt
const-iterator to indices of points during kd-tree construction
Definition: nabo_private.h:115
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node::cutVal
T cutVal
for split node, split value
Definition: nabo_private.h:143
Nabo
Namespace for Nabo.
Definition: experimental/kdtree_cpu.cpp:40
index_heap.h
implementation of index heaps
Nabo::Parameters
Parameter vector.
Definition: nabo.h:231
nabo_private.h
header for implementation
Nabo::argMax
size_t argMax(const typename NearestNeighbourSearch< T, CloudType >::Vector &v)
Return the index of the maximum value of a vector of positive values.
Definition: experimental/kdtree_cpu.cpp:45
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node
search node
Definition: nabo_private.h:138
std::swap
void swap(linb::any &lhs, linb::any &rhs) noexcept
Definition: any.hpp:452
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt
KDTree, unbalanced, points in leaves, stack, implicit bounds, ANN_KD_SL_MIDPT, optimised implementati...
Definition: nabo_private.h:94
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::maxBound
const Vector maxBound
the high bound of the search space (axis-aligned bounding box)
Definition: nabo.h:282
Nabo::runtime_error
Definition: nabo/nabo.cpp:50
_UNUSED
#define _UNUSED
Definition: nabo_private.h:50
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::nodes
Nodes nodes
search nodes
Definition: nabo_private.h:174
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::dimBitCount
const uint32_t dimBitCount
number of bits required to store dimension index + number of dimensions
Definition: nabo_private.h:121
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt
KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt(const CloudType &cloud, const Index dim, const unsigned creationOptionFlags, const Parameters &additionalParameters)
constructor, calls NearestNeighbourSearch<T>(cloud)
Definition: nabo/kdtree_cpu.cpp:228
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::cloud
const CloudType & cloud
the reference to the data-point cloud, which must remain valid during the lifetime of the NearestNeig...
Definition: nabo.h:274
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Vector
NearestNeighbourSearch< T, CloudType >::Vector Vector
Definition: nabo_private.h:96
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BucketEntry::pt
const T * pt
pointer to first value of point data, 0 if end of bucket
Definition: nabo_private.h:160
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BuildPoints
std::vector< Index > BuildPoints
indices of points during kd-tree construction
Definition: nabo_private.h:111
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::createDimChildBucketSize
uint32_t createDimChildBucketSize(const uint32_t dim, const uint32_t childIndex) const
create the compound index containing the dimension and the index of the child or the bucket size
Definition: nabo_private.h:126
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BucketEntry::index
Index index
index of point
Definition: nabo_private.h:161
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::onePointKnn
unsigned long onePointKnn(const Matrix &query, IndexMatrix &indices, Matrix &dists2, int i, Heap &heap, std::vector< T > &off, const T maxError, const T maxRadius2, const bool allowSelfMatch, const bool collectStatistics, const bool sortResults) const
search one point, call recurseKnn with the correct template parameters
Definition: nabo/kdtree_cpu.cpp:339
Nabo::NearestNeighbourSearch
Nearest neighbour search interface, templatized on scalar type.
Definition: nabo.h:258
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BucketEntry
entry in a bucket
Definition: nabo_private.h:158
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::recurseKnn
unsigned long recurseKnn(const T *query, const unsigned n, T rd, Heap &heap, std::vector< T > &off, const T maxError, const T maxRadius2) const
recursive search, strongly inspired by ANN and [Arya & Mount, Algorithms for fast vector quantization...
Definition: nabo/kdtree_cpu.cpp:368
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::knn
virtual unsigned long knn(const Matrix &query, IndexMatrix &indices, Matrix &dists2, const Index k, const T epsilon, const unsigned optionFlags, const T maxRadius) const
Definition: nabo/kdtree_cpu.cpp:275
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::IndexMatrix
NearestNeighbourSearch< T, CloudType >::IndexMatrix IndexMatrix
Definition: nabo_private.h:100
Nabo::getStorageBitCount
T getStorageBitCount(T v)
Return the number of bit required to store a value.
Definition: nabo/kdtree_cpu.cpp:61
Nabo::NearestNeighbourSearch< T, Eigen::Matrix< T, Eigen::Dynamic, Eigen::Dynamic > >::minBound
const Vector minBound
the low bound of the search space (axis-aligned bounding box)
Definition: nabo.h:280
std
Definition: any.hpp:450
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::bucketSize
const unsigned bucketSize
size of bucket
Definition: nabo_private.h:118
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::buildNodes
unsigned buildNodes(const BuildPointsIt first, const BuildPointsIt last, const Vector minValues, const Vector maxValues)
construct nodes for points [first..last[ inside the hyperrectangle [minValues..maxValues]
Definition: nabo/kdtree_cpu.cpp:110
NearestNeighbourSearch
Definition: python/nabo.cpp:95
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node::dimChildBucketSize
uint32_t dimChildBucketSize
cut dimension for split nodes (dimBitCount lsb), index of right node or number of bucket(rest)....
Definition: nabo_private.h:140
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::BuildPointsIt
BuildPoints::iterator BuildPointsIt
iterator to indices of points during kd-tree construction
Definition: nabo_private.h:113
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Matrix
NearestNeighbourSearch< T, CloudType >::Matrix Matrix
Definition: nabo_private.h:97
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Node::bucketIndex
uint32_t bucketIndex
for leaf node, pointer to bucket
Definition: nabo_private.h:144
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::buckets
Buckets buckets
buckets
Definition: nabo_private.h:177
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::getBounds
std::pair< T, T > getBounds(const BuildPointsIt first, const BuildPointsIt last, const unsigned dim)
return the bounds of points from [first..last[ on dimension dim
Definition: nabo/kdtree_cpu.cpp:94
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt::Index
NearestNeighbourSearch< T, CloudType >::Index Index
Definition: nabo_private.h:98


libnabo
Author(s): Stéphane Magnenat
autogenerated on Fri Aug 2 2024 08:39:11