00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #include "nabo_experimental.h"
00033 #include "../nabo/index_heap.h"
00034 #include <iostream>
00035 #include <stdexcept>
00036 #include <limits>
00037 #include <queue>
00038 #include <algorithm>
00039 #include <boost/numeric/conversion/bounds.hpp>
00040 #include <boost/limits.hpp>
00041
00042 namespace Nabo
00043 {
00044 using namespace std;
00045
00046 template<typename T, typename CloudType>
00047 size_t argMax(const typename NearestNeighbourSearch<T, CloudType>::Vector& v)
00048 {
00049 T maxVal(0);
00050 size_t maxIdx(0);
00051 for (int i = 0; i < v.size(); ++i)
00052 {
00053 if (v[i] > maxVal)
00054 {
00055 maxVal = v[i];
00056 maxIdx = i;
00057 }
00058 }
00059 return maxIdx;
00060 }
00061
00062 template<typename T, typename CloudType>
00063 size_t KDTreeBalancedPtInNodes<T, CloudType>::getTreeSize(size_t elCount) const
00064 {
00065
00066 size_t count = 0;
00067 int i = 31;
00068 for (; i >= 0; --i)
00069 {
00070 if (elCount & (1 << i))
00071 break;
00072 }
00073 for (int j = 0; j <= i; ++j)
00074 count |= (1 << j);
00075
00076 return count;
00077 }
00078
00079 template<typename T, typename CloudType>
00080 typename KDTreeBalancedPtInNodes<T, CloudType>::IndexVector KDTreeBalancedPtInNodes<T, CloudType>::cloudIndexesFromNodesIndexes(const IndexVector& indexes) const
00081 {
00082 IndexVector cloudIndexes(indexes.size());
00083 for (int i = 0; i < indexes.size(); ++i)
00084 cloudIndexes.coeffRef(i) = nodes[indexes[i]].index;
00085 return cloudIndexes;
00086 }
00087
00088 template<typename T, typename CloudType>
00089 void KDTreeBalancedPtInNodes<T, CloudType>::buildNodes(const BuildPointsIt first, const BuildPointsIt last, const size_t pos)
00090 {
00091 const size_t count(last - first);
00092
00093 if (count == 1)
00094 {
00095 nodes[pos] = Node(first->pos, -1, first->index);
00096 return;
00097 }
00098
00099
00100
00101 Vector mean(Vector::Zero(this->dim));
00102 for (BuildPointsCstIt it(first); it != last; ++it)
00103 mean += it->pos;
00104 mean /= last - first;
00105
00106 Vector var(Vector::Zero(this->dim));
00107 for (BuildPointsCstIt it(first); it != last; ++it)
00108 var += (it->pos - mean).cwise() * (it->pos - mean);
00109
00110 const size_t cutDim = argMax<T>(var);
00111
00112
00113 sort(first, last, CompareDim(cutDim));
00114
00115
00116 const size_t recurseCount(count-1);
00117 const size_t rightCount(recurseCount/2);
00118 const size_t leftCount(recurseCount-rightCount);
00119 assert(last - rightCount == first + leftCount + 1);
00120
00121 nodes[pos] = Node((first+leftCount)->pos, cutDim, (first+leftCount)->index);
00122
00123
00124
00125
00126 if (count > 2)
00127 {
00128 buildNodes(first, first + leftCount, childLeft(pos));
00129 buildNodes(first + leftCount + 1, last, childRight(pos));
00130 }
00131 else
00132 {
00133 nodes[childLeft(pos)] = Node(first->pos, -1, first->index);
00134 nodes[childRight(pos)] = Node(Vector(), -2, 0);
00135 }
00136 }
00137
00138 template<typename T, typename CloudType>
00139 void KDTreeBalancedPtInNodes<T, CloudType>::dump(const Vector minValues, const Vector maxValues, const size_t pos) const
00140 {
00141 const Node& node(nodes[pos]);
00142
00143 if (node.dim >= -1)
00144 {
00145 if (this->dim == 2)
00146 cout << "<circle cx=\"" << 100*node.pos(0) << "\" cy=\"" << 100*node.pos(1) << "\" r=\"1\" stroke=\"black\" stroke-width=\"0.2\" fill=\"red\"/>" << endl;
00147 else
00148 cout << "pt at\n" << node.pos << endl;
00149 }
00150 if (node.dim >= 0)
00151 {
00152
00153
00154
00155 Vector leftMaxValues(maxValues);
00156 leftMaxValues[node.dim] = node.pos[node.dim];
00157
00158 Vector rightMinValues(minValues);
00159 rightMinValues[node.dim] = node.pos[node.dim];
00160
00161
00162 if (this->dim == 2)
00163 cout << "<line x1=\"" << 100*rightMinValues(0) << "\" y1=\"" << 100*rightMinValues(1) << "\" x2=\"" << 100*leftMaxValues(0) << "\" y2=\"" << 100*leftMaxValues(1) << "\" style=\"stroke:rgb(0,0,0);stroke-width:0.2\"/>" << endl;
00164 else
00165 cout << "cut from\n" << rightMinValues << "\nto\n" << leftMaxValues << endl;
00166
00167 dump(minValues, leftMaxValues, childLeft(pos));
00168 dump(rightMinValues, maxValues, childRight(pos));
00169 }
00170 }
00171
00172 template<typename T, typename CloudType>
00173 KDTreeBalancedPtInNodes<T, CloudType>::KDTreeBalancedPtInNodes(const CloudType& cloud):
00174 NearestNeighbourSearch<T, CloudType>::NearestNeighbourSearch(cloud)
00175 {
00176
00177 BuildPoints buildPoints;
00178 buildPoints.reserve(cloud.cols());
00179 for (int i = 0; i < cloud.cols(); ++i)
00180 {
00181 const Vector& v(cloud.col(i));
00182 buildPoints.push_back(BuildPoint(v, i));
00183 const_cast<Vector&>(this->minBound) = this->minBound.cwise().min(v);
00184 const_cast<Vector&>(this->maxBound) = this->maxBound.cwise().max(v);
00185 }
00186
00187
00188 nodes.resize(getTreeSize(cloud.cols()));
00189 buildNodes(buildPoints.begin(), buildPoints.end(), 0);
00190
00191
00192
00193 }
00194
00195
00196
00197 template<typename T, typename CloudType>
00198 KDTreeBalancedPtInNodesPQ<T, CloudType>::KDTreeBalancedPtInNodesPQ(const CloudType& cloud):
00199 KDTreeBalancedPtInNodes<T, CloudType>::KDTreeBalancedPtInNodes(cloud)
00200 {
00201 }
00202
00203 template<typename T, typename CloudType>
00204 typename KDTreeBalancedPtInNodesPQ<T, CloudType>::IndexVector KDTreeBalancedPtInNodesPQ<T, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00205 {
00206 typedef priority_queue<SearchElement> Queue;
00207
00208 const T maxError(1 + epsilon);
00209 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T>::ALLOW_SELF_MATCH);
00210
00211 Queue queue;
00212 queue.push(SearchElement(0, 0));
00213 IndexHeapSTL<Index, T> heap(k);
00214 statistics.lastQueryVisitCount = 0;
00215
00216 while (!queue.empty())
00217 {
00218 SearchElement el(queue.top());
00219 queue.pop();
00220
00221
00222 if (el.minDist * maxError > heap.headValue())
00223 break;
00224
00225 size_t n(el.index);
00226 while (1)
00227 {
00228 const Node& node(nodes[n]);
00229 assert (node.dim != -2);
00230
00231
00232 const T dist(dist2<T>(node.pos, query));
00233 if ((dist < heap.headValue()) &&
00234 (allowSelfMatch || (dist > numeric_limits<T>::epsilon())))
00235 heap.replaceHead(n, dist);
00236
00237
00238 if (node.dim < 0)
00239 break;
00240
00241 const T offset(query.coeff(node.dim) - node.pos.coeff(node.dim));
00242 const T offset2(offset * offset);
00243 const T bestDist(heap.headValue());
00244 if (offset > 0)
00245 {
00246
00247 if (offset2 < bestDist && nodes[childLeft(n)].dim != -2)
00248 queue.push(SearchElement(childLeft(n), offset2));
00249
00250 if (nodes[childRight(n)].dim != -2)
00251 n = childRight(n);
00252 else
00253 break;
00254 }
00255 else
00256 {
00257
00258 if (offset2 < bestDist && nodes[childRight(n)].dim != -2)
00259 queue.push(SearchElement(childRight(n), offset2));
00260
00261 if (nodes[childLeft(n)].dim != -2)
00262 n = childLeft(n);
00263 else
00264 break;
00265 }
00266 ++statistics.lastQueryVisitCount;
00267 }
00268 }
00269 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00270
00271 if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00272 heap.sort();
00273
00274 return cloudIndexesFromNodesIndexes(heap.getIndexes());
00275 }
00276
00277 template struct KDTreeBalancedPtInNodesPQ<float>;
00278 template struct KDTreeBalancedPtInNodesPQ<double>;
00279 template struct KDTreeBalancedPtInNodesPQ<float, Eigen::Matrix3Xf>;
00280 template struct KDTreeBalancedPtInNodesPQ<double, Eigen::Matrix3Xd>;
00281 template struct KDTreeBalancedPtInNodesPQ<float, Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00282 template struct KDTreeBalancedPtInNodesPQ<double, Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00283
00284
00285
00286 template<typename T, typename CloudType>
00287 KDTreeBalancedPtInNodesStack<T, CloudType>::KDTreeBalancedPtInNodesStack(const CloudType& cloud):
00288 KDTreeBalancedPtInNodes<T, CloudType>::KDTreeBalancedPtInNodes(cloud)
00289 {
00290 }
00291
00292 template<typename T, typename CloudType>
00293 typename KDTreeBalancedPtInNodesStack<T, CloudType>::IndexVector KDTreeBalancedPtInNodesStack<T, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00294 {
00295 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T>::ALLOW_SELF_MATCH);
00296
00297 assert(nodes.size() > 0);
00298 assert(nodes[0].pos.size() == query.size());
00299 Heap heap(k);
00300 Vector off(Vector::Zero(nodes[0].pos.size()));
00301
00302 statistics.lastQueryVisitCount = 0;
00303
00304 recurseKnn(query, 0, 0, heap, off, 1 + epsilon, allowSelfMatch);
00305
00306 if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00307 heap.sort();
00308
00309 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00310
00311 return cloudIndexesFromNodesIndexes(heap.getIndexes());
00312 }
00313
00314 template<typename T, typename CloudType>
00315 void KDTreeBalancedPtInNodesStack<T, CloudType>::recurseKnn(const Vector& query, const size_t n, T rd, Heap& heap, Vector& off, const T maxError, const bool allowSelfMatch)
00316 {
00317 const Node& node(nodes[n]);
00318 const int cd(node.dim);
00319
00320 ++statistics.lastQueryVisitCount;
00321
00322 if (cd == -2)
00323 return;
00324
00325 const T dist(dist2<T, CloudType>(node.pos, query));
00326 if ((dist < heap.headValue()) &&
00327 (allowSelfMatch || (dist > numeric_limits<T>::epsilon()))
00328 )
00329 heap.replaceHead(n, dist);
00330
00331 if (cd != -1)
00332 {
00333 const T old_off(off.coeff(cd));
00334 const T new_off(query.coeff(cd) - node.pos.coeff(cd));
00335 if (new_off > 0)
00336 {
00337 recurseKnn(query, childRight(n), rd, heap, off, maxError, allowSelfMatch);
00338 rd += - old_off*old_off + new_off*new_off;
00339 if (rd * maxError < heap.headValue())
00340 {
00341 off.coeffRef(cd) = new_off;
00342 recurseKnn(query, childLeft(n), rd, heap, off, maxError, allowSelfMatch);
00343 off.coeffRef(cd) = old_off;
00344 }
00345 }
00346 else
00347 {
00348 recurseKnn(query, childLeft(n), rd, heap, off, maxError, allowSelfMatch);
00349 rd += - old_off*old_off + new_off*new_off;
00350 if (rd * maxError < heap.headValue())
00351 {
00352 off.coeffRef(cd) = new_off;
00353 recurseKnn(query, childRight(n), rd, heap, off, maxError, allowSelfMatch);
00354 off.coeffRef(cd) = old_off;
00355 }
00356 }
00357 }
00358 }
00359
00360 template struct KDTreeBalancedPtInNodesStack<float>;
00361 template struct KDTreeBalancedPtInNodesStack<double>;
00362 template struct KDTreeBalancedPtInNodesStack<float, Eigen::Matrix3Xf>;
00363 template struct KDTreeBalancedPtInNodesStack<double, Eigen::Matrix3Xd>;
00364 template struct KDTreeBalancedPtInNodesStack<float, Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00365 template struct KDTreeBalancedPtInNodesStack<double, Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00366
00367
00368
00369 template<typename T, typename CloudType>
00370 size_t KDTreeBalancedPtInLeavesStack<T, CloudType>::getTreeSize(size_t elCount) const
00371 {
00372
00373 assert(elCount > 0);
00374 elCount --;
00375 size_t count = 0;
00376 int i = 31;
00377 for (; i >= 0; --i)
00378 {
00379 if (elCount & (1 << i))
00380 break;
00381 }
00382 for (int j = 0; j <= i; ++j)
00383 count |= (1 << j);
00384 count <<= 1;
00385 count |= 1;
00386 return count;
00387 }
00388
00389 template<typename T, typename CloudType>
00390 void KDTreeBalancedPtInLeavesStack<T, CloudType>::buildNodes(const BuildPointsIt first, const BuildPointsIt last, const size_t pos, const Vector minValues, const Vector maxValues, const bool balanceVariance)
00391 {
00392 const size_t count(last - first);
00393
00394 if (count == 1)
00395 {
00396 const int dim = -2-(first->index);
00397 assert(pos < nodes.size());
00398 nodes[pos] = Node(dim);
00399 return;
00400 }
00401
00402 size_t cutDim;
00403 if (balanceVariance)
00404 {
00405
00406
00407 Vector mean(Vector::Zero(this->dim));
00408 for (BuildPointsCstIt it(first); it != last; ++it)
00409 mean += it->pos;
00410 mean /= last - first;
00411
00412 Vector var(Vector::Zero(this->dim));
00413 for (BuildPointsCstIt it(first); it != last; ++it)
00414 var += (it->pos - mean).cwise() * (it->pos - mean);
00415
00416 cutDim = argMax<T>(var);
00417 }
00418 else
00419 {
00420
00421 cutDim = argMax<T>(maxValues - minValues);
00422 }
00423
00424
00425 const size_t rightCount(count/2);
00426 const size_t leftCount(count - rightCount);
00427 assert(last - rightCount == first + leftCount);
00428
00429
00430
00431 nth_element(first, first + leftCount, last, CompareDim(cutDim));
00432
00433
00434 const T cutVal((first+leftCount)->pos.coeff(cutDim));
00435 nodes[pos] = Node(cutDim, cutVal);
00436
00437
00438
00439
00440 Vector leftMaxValues(maxValues);
00441 leftMaxValues[cutDim] = cutVal;
00442
00443 Vector rightMinValues(minValues);
00444 rightMinValues[cutDim] = cutVal;
00445
00446
00447 buildNodes(first, first + leftCount, childLeft(pos), minValues, leftMaxValues, balanceVariance);
00448 buildNodes(first + leftCount, last, childRight(pos), rightMinValues, maxValues, balanceVariance);
00449 }
00450
00451 template<typename T, typename CloudType>
00452 KDTreeBalancedPtInLeavesStack<T, CloudType>::KDTreeBalancedPtInLeavesStack(const CloudType& cloud, const bool balanceVariance):
00453 NearestNeighbourSearch<T, CloudType>::NearestNeighbourSearch(cloud)
00454 {
00455
00456 BuildPoints buildPoints;
00457 buildPoints.reserve(cloud.cols());
00458 for (int i = 0; i < cloud.cols(); ++i)
00459 {
00460 const Vector& v(cloud.col(i));
00461 buildPoints.push_back(BuildPoint(v, i));
00462 const_cast<Vector&>(minBound) = minBound.cwise().min(v);
00463 const_cast<Vector&>(maxBound) = maxBound.cwise().max(v);
00464 }
00465
00466
00467 nodes.resize(getTreeSize(cloud.cols()));
00468 buildNodes(buildPoints.begin(), buildPoints.end(), 0, minBound, maxBound, balanceVariance);
00469
00470
00471 }
00472
00473 template<typename T, typename CloudType>
00474 typename KDTreeBalancedPtInLeavesStack<T, CloudType>::IndexVector KDTreeBalancedPtInLeavesStack<T, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00475 {
00476 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T, CloudType>::ALLOW_SELF_MATCH);
00477
00478 assert(nodes.size() > 0);
00479 Heap heap(k);
00480 Vector off(Vector::Zero(query.size()));
00481
00482 statistics.lastQueryVisitCount = 0;
00483
00484 recurseKnn(query, 0, 0, heap, off, 1 + epsilon, allowSelfMatch);
00485
00486 if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00487 heap.sort();
00488
00489 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00490
00491 return heap.getIndexes();
00492 }
00493
00494 template<typename T, typename CloudType>
00495 void KDTreeBalancedPtInLeavesStack<T, CloudType>::recurseKnn(const Vector& query, const size_t n, T rd, Heap& heap, Vector& off, const T maxError, const bool allowSelfMatch)
00496 {
00497 const Node& node(nodes[n]);
00498 const int cd(node.dim);
00499
00500 ++statistics.lastQueryVisitCount;
00501
00502 if (cd < 0)
00503 {
00504 if (cd == -1)
00505 return;
00506 const int index(-(cd + 2));
00507 const T dist(dist2<T>(query, cloud.col(index)));
00508 if ((dist < heap.headValue()) &&
00509 (allowSelfMatch || (dist > numeric_limits<T>::epsilon()))
00510 )
00511 heap.replaceHead(index, dist);
00512 }
00513 else
00514 {
00515 const T old_off(off.coeff(cd));
00516 const T new_off(query.coeff(cd) - node.cutVal);
00517 if (new_off > 0)
00518 {
00519 recurseKnn(query, childRight(n), rd, heap, off, maxError, allowSelfMatch);
00520 rd += - old_off*old_off + new_off*new_off;
00521 if (rd * maxError < heap.headValue())
00522 {
00523 off.coeffRef(cd) = new_off;
00524 recurseKnn(query, childLeft(n), rd, heap, off, maxError, allowSelfMatch);
00525 off.coeffRef(cd) = old_off;
00526 }
00527 }
00528 else
00529 {
00530 recurseKnn(query, childLeft(n), rd, heap, off, maxError, allowSelfMatch);
00531 rd += - old_off*old_off + new_off*new_off;
00532 if (rd * maxError < heap.headValue())
00533 {
00534 off.coeffRef(cd) = new_off;
00535 recurseKnn(query, childRight(n), rd, heap, off, maxError, allowSelfMatch);
00536 off.coeffRef(cd) = old_off;
00537 }
00538 }
00539 }
00540 }
00541
00542 template struct KDTreeBalancedPtInLeavesStack<float>;
00543 template struct KDTreeBalancedPtInLeavesStack<double>;
00544 template struct KDTreeBalancedPtInLeavesStack<float, Eigen::Matrix3Xf>;
00545 template struct KDTreeBalancedPtInLeavesStack<double, Eigen::Matrix3Xd>;
00546 template struct KDTreeBalancedPtInLeavesStack<float, Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00547 template struct KDTreeBalancedPtInLeavesStack<double, Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00548
00549
00550
00551 template<typename T, typename Heap, typename CloudType>
00552 unsigned KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::buildNodes(const BuildPointsIt first, const BuildPointsIt last, const Vector minValues, const Vector maxValues)
00553 {
00554 const size_t count(last - first);
00555 const unsigned pos(nodes.size());
00556
00557
00558 if (count == 1)
00559 {
00560 nodes.push_back(Node(first->index));
00561 return pos;
00562 }
00563
00564
00565 const unsigned cutDim = argMax<T>(maxValues - minValues);
00566 T cutVal((maxValues(cutDim) + minValues(cutDim))/2);
00567
00568
00569
00570 sort(first, last, CompareDim(cutDim));
00571
00572
00573 size_t rightStart(0);
00574 while (rightStart < count && (first+rightStart)->pos.coeff(cutDim) < cutVal)
00575 ++rightStart;
00576
00577
00578 if (rightStart == 0)
00579 {
00580 cutVal = first->pos.coeff(cutDim);
00581 rightStart = 1;
00582 }
00583 else if (rightStart == count)
00584 {
00585 rightStart = count - 1;
00586 cutVal = (first + rightStart)->pos.coeff(cutDim);
00587 }
00588
00589
00590 Vector leftMaxValues(maxValues);
00591 leftMaxValues[cutDim] = cutVal;
00592
00593 Vector rightMinValues(minValues);
00594 rightMinValues[cutDim] = cutVal;
00595
00596
00597 const size_t rightCount(count - rightStart);
00598 const size_t leftCount(count - rightCount);
00599
00600
00601 nodes.push_back(Node(cutDim, cutVal, 0));
00602
00603
00604 const unsigned __attribute__ ((unused)) leftChild = buildNodes(first, first + leftCount, minValues, leftMaxValues);
00605 assert(leftChild == pos + 1);
00606 const unsigned rightChild = buildNodes(first + leftCount, last, rightMinValues, maxValues);
00607
00608
00609 nodes[pos].rightChild = rightChild;
00610 return pos;
00611 }
00612
00613 template<typename T, typename Heap, typename CloudType>
00614 KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::KDTreeUnbalancedPtInLeavesImplicitBoundsStack(const CloudType& cloud):
00615 NearestNeighbourSearch<T, CloudType>::NearestNeighbourSearch(cloud)
00616 {
00617
00618 BuildPoints buildPoints;
00619 buildPoints.reserve(cloud.cols());
00620 for (int i = 0; i < cloud.cols(); ++i)
00621 {
00622 const Vector& v(cloud.col(i));
00623 buildPoints.push_back(BuildPoint(v, i));
00624 const_cast<Vector&>(minBound) = minBound.cwise().min(v);
00625 const_cast<Vector&>(maxBound) = maxBound.cwise().max(v);
00626 }
00627
00628
00629
00630 buildNodes(buildPoints.begin(), buildPoints.end(), minBound, maxBound);
00631
00632
00633 }
00634
00635 template<typename T, typename Heap, typename CloudType>
00636 typename KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::IndexVector KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00637 {
00638 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T, CloudType>::ALLOW_SELF_MATCH);
00639
00640 assert(nodes.size() > 0);
00641 Heap heap(k);
00642 Vector off(Vector::Zero(query.size()));
00643
00644 statistics.lastQueryVisitCount = 0;
00645
00646 recurseKnn(query, 0, 0, heap, off, 1+epsilon, allowSelfMatch);
00647
00648 if (optionFlags & NearestNeighbourSearch<T, CloudType>::SORT_RESULTS)
00649 heap.sort();
00650
00651 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00652
00653 return heap.getIndexes();
00654 }
00655
00656 template<typename T, typename Heap, typename CloudType>
00657 typename KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::IndexMatrix KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::knnM(const Matrix& query, const Index k, const T epsilon, const unsigned optionFlags)
00658 {
00659 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T, CloudType>::ALLOW_SELF_MATCH);
00660 assert(nodes.size() > 0);
00661
00662 assert(nodes.size() > 0);
00663 Heap heap(k);
00664 Vector off(query.rows());
00665
00666 IndexMatrix result(k, query.cols());
00667 const int colCount(query.cols());
00668
00669 for (int i = 0; i < colCount; ++i)
00670 {
00671 const Vector& q(query.col(i));
00672
00673 off.setZero();
00674 heap.reset();
00675
00676 statistics.lastQueryVisitCount = 0;
00677
00678 recurseKnn(q, 0, 0, heap, off, 1+epsilon, allowSelfMatch);
00679
00680 if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00681 heap.sort();
00682
00683 result.col(i) = heap.getIndexes();
00684
00685 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00686 }
00687
00688 return result;
00689 }
00690
00691 template<typename T, typename Heap, typename CloudType>
00692 void KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::recurseKnn(const Vector& query, const unsigned n, T rd, Heap& heap, Vector& off, const T maxError, const bool allowSelfMatch)
00693 {
00694 const Node& node(nodes[n]);
00695
00696
00697 if (node.rightChild == Node::INVALID_CHILD)
00698 {
00699 const unsigned index(node.ptIndex);
00700
00701
00702 T dist(0);
00703 const T* qPtr(&query.coeff(0));
00704 const T* dPtr(&cloud.coeff(0, index));
00705 const int dim(query.size());
00706 for (int i = 0; i < dim; ++i)
00707 {
00708 const T diff(*qPtr - *dPtr);
00709 dist += diff*diff;
00710 qPtr++; dPtr++;
00711 }
00712 if ((dist < heap.headValue()) &&
00713 (allowSelfMatch || (dist > numeric_limits<T>::epsilon()))
00714 )
00715 heap.replaceHead(index, dist);
00716 }
00717 else
00718 {
00719 const unsigned cd(node.dim);
00720 const T old_off(off.coeff(cd));
00721 const T new_off(query.coeff(cd) - node.cutVal);
00722 if (new_off > 0)
00723 {
00724 recurseKnn(query, node.rightChild, rd, heap, off, maxError, allowSelfMatch);
00725 rd += - old_off*old_off + new_off*new_off;
00726 if (rd * maxError < heap.headValue())
00727 {
00728 off.coeffRef(cd) = new_off;
00729 recurseKnn(query, n + 1, rd, heap, off, maxError, allowSelfMatch);
00730 off.coeffRef(cd) = old_off;
00731 }
00732 }
00733 else
00734 {
00735 recurseKnn(query, n+1, rd, heap, off, maxError, allowSelfMatch);
00736 rd += - old_off*old_off + new_off*new_off;
00737 if (rd * maxError < heap.headValue())
00738 {
00739 off.coeffRef(cd) = new_off;
00740 recurseKnn(query, node.rightChild, rd, heap, off, maxError, allowSelfMatch);
00741 off.coeffRef(cd) = old_off;
00742 }
00743 }
00744 }
00745 }
00746
00747 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapSTL<int,float>>;
00748 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapBruteForceVector<int,float>>;
00749 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapSTL<int,double>>;
00750 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapBruteForceVector<int,double>>;
00751
00752 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapSTL<int,float>,Eigen::Matrix3Xf>;
00753 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapBruteForceVector<int,float>,Eigen::Matrix3Xf>;
00754 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapSTL<int,double>,Eigen::Matrix3Xd>;
00755 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapBruteForceVector<int,double>,Eigen::Matrix3Xd>;
00756
00757 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapSTL<int,float>,Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00758 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapBruteForceVector<int,float>,Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00759 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapSTL<int,double>,Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00760 template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapBruteForceVector<int,double>,Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00761
00762 template<typename T, typename CloudType>
00763 unsigned KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::buildNodes(const BuildPointsIt first, const BuildPointsIt last, const Vector minValues, const Vector maxValues)
00764 {
00765 const size_t count(last - first);
00766 const unsigned pos(nodes.size());
00767
00768
00769 if (count == 1)
00770 {
00771 const int dim = -1-(first->index);
00772 nodes.push_back(Node(dim));
00773 return pos;
00774 }
00775
00776
00777 const int cutDim = argMax<T>(maxValues - minValues);
00778 T cutVal((maxValues(cutDim) + minValues(cutDim))/2);
00779
00780
00781
00782 sort(first, last, CompareDim(cutDim));
00783
00784
00785 size_t rightStart(0);
00786 while (rightStart < count && (first+rightStart)->pos.coeff(cutDim) < cutVal)
00787 ++rightStart;
00788
00789
00790 if (rightStart == 0)
00791 {
00792 cutVal = first->pos.coeff(cutDim);
00793 rightStart = 1;
00794 }
00795 else if (rightStart == count)
00796 {
00797 rightStart = count - 1;
00798 cutVal = (first + rightStart)->pos.coeff(cutDim);
00799 }
00800
00801
00802 Vector leftMaxValues(maxValues);
00803 leftMaxValues[cutDim] = cutVal;
00804
00805 Vector rightMinValues(minValues);
00806 rightMinValues[cutDim] = cutVal;
00807
00808
00809 const size_t rightCount(count - rightStart);
00810 const size_t leftCount(count - rightCount);
00811
00812
00813 nodes.push_back(Node(cutDim, cutVal, minValues.coeff(cutDim), maxValues.coeff(cutDim)));
00814
00815
00816 const unsigned __attribute__ ((unused)) leftChild = buildNodes(first, first + leftCount, minValues, leftMaxValues);
00817 assert(leftChild == pos + 1);
00818 const unsigned rightChild = buildNodes(first + leftCount, last, rightMinValues, maxValues);
00819
00820
00821 nodes[pos].rightChild = rightChild;
00822 return pos;
00823 }
00824
00825 template<typename T, typename CloudType>
00826 KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::KDTreeUnbalancedPtInLeavesExplicitBoundsStack(const CloudType& cloud):
00827 NearestNeighbourSearch<T, CloudType>::NearestNeighbourSearch(cloud)
00828 {
00829
00830 BuildPoints buildPoints;
00831 buildPoints.reserve(cloud.cols());
00832 for (int i = 0; i < cloud.cols(); ++i)
00833 {
00834 const Vector& v(cloud.col(i));
00835 buildPoints.push_back(BuildPoint(v, i));
00836 const_cast<Vector&>(minBound) = minBound.cwise().min(v);
00837 const_cast<Vector&>(maxBound) = maxBound.cwise().max(v);
00838 }
00839
00840
00841
00842 buildNodes(buildPoints.begin(), buildPoints.end(), minBound, maxBound);
00843
00844
00845 }
00846
00847 template<typename T, typename CloudType>
00848 typename KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::IndexVector KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00849 {
00850 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T, CloudType>::ALLOW_SELF_MATCH);
00851
00852 assert(nodes.size() > 0);
00853 Heap heap(k);
00854
00855 statistics.lastQueryVisitCount = 0;
00856
00857 recurseKnn(query, 0, 0, heap, 1+epsilon, allowSelfMatch);
00858
00859 if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00860 heap.sort();
00861
00862 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00863
00864 return heap.getIndexes();
00865 }
00866
00867 template<typename T, typename CloudType>
00868 void KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::recurseKnn(const Vector& query, const size_t n, T rd, Heap& heap, const T maxError, const bool allowSelfMatch)
00869 {
00870 const Node& node(nodes[n]);
00871 const int cd(node.dim);
00872
00873 ++statistics.lastQueryVisitCount;
00874
00875 if (cd < 0)
00876 {
00877 const int index(-(cd + 1));
00878 const T dist(dist2<T>(query, cloud.col(index)));
00879 if ((dist < heap.headValue()) &&
00880 (allowSelfMatch || (dist > numeric_limits<T>::epsilon()))
00881 )
00882 heap.replaceHead(index, dist);
00883 }
00884 else
00885 {
00886 const T q_val(query.coeff(cd));
00887 const T cut_diff(q_val - node.cutVal);
00888 if (cut_diff < 0)
00889 {
00890 recurseKnn(query, n+1, rd, heap, maxError, allowSelfMatch);
00891
00892 T box_diff = node.lowBound - q_val;
00893 if (box_diff < 0)
00894 box_diff = 0;
00895
00896 rd += cut_diff*cut_diff - box_diff*box_diff;
00897
00898 if (rd * maxError < heap.headValue())
00899 recurseKnn(query, node.rightChild, rd, heap, maxError, allowSelfMatch);
00900 }
00901 else
00902 {
00903 recurseKnn(query, node.rightChild, rd, heap, maxError, allowSelfMatch);
00904
00905 T box_diff = q_val - node.highBound;
00906 if (box_diff < 0)
00907 box_diff = 0;
00908
00909 rd += cut_diff*cut_diff - box_diff*box_diff;
00910
00911 if (rd * maxError < heap.headValue())
00912 recurseKnn(query, n + 1, rd, heap, maxError, allowSelfMatch);
00913 }
00914 }
00915 }
00916
00917 template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<float>;
00918 template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<double>;
00919 template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<float, Eigen::Matrix3Xf>;
00920 template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<double, Eigen::Matrix3Xd>;
00921 template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<float, Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00922 template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<double, Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00923 }