1 /*********************************************************************** 2 * Software License Agreement (BSD License) 3 * 4 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. 5 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved. 6 * 7 * THE BSD LICENSE 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 *************************************************************************/ 30 31 #ifndef FLANN_RESULTSET_H 32 #define FLANN_RESULTSET_H 33 34 #include <algorithm> 35 #include <cstring> 36 #include <iostream> 37 #include <limits> 38 #include <set> 39 #include <vector> 40 41 namespace flann 42 { 43 44 /* This record represents a branch point when finding neighbors in 45 the tree. It contains a record of the minimum distance to the query 46 point, as well as the node at which the search resumes. 47 */ 48 49 template <typename T, typename DistanceType> 50 struct BranchStruct 51 { 52 T node; /* Tree node at which search resumes */ 53 DistanceType mindist; /* Minimum distance to query for all nodes below. */ 54 BranchStructBranchStruct55 BranchStruct() {} BranchStructBranchStruct56 BranchStruct(const T& aNode, DistanceType dist) : node(aNode), mindist(dist) {} 57 58 bool operator<(const BranchStruct<T, DistanceType>& rhs) const 59 { 60 return mindist<rhs.mindist; 61 } 62 }; 63 64 65 template <typename DistanceType> 66 struct DistanceIndex 67 { DistanceIndexDistanceIndex68 DistanceIndex(DistanceType dist, size_t index) : 69 dist_(dist), index_(index) 70 { 71 } 72 bool operator<(const DistanceIndex& dist_index) const 73 { 74 return (dist_ < dist_index.dist_) || ((dist_ == dist_index.dist_) && index_ < dist_index.index_); 75 } 76 DistanceType dist_; 77 size_t index_; 78 }; 79 80 81 template <typename DistanceType> 82 class ResultSet 83 { 84 public: ~ResultSet()85 virtual ~ResultSet() {} 86 87 virtual bool full() const = 0; 88 89 virtual void addPoint(DistanceType dist, size_t index) = 0; 90 91 virtual DistanceType worstDist() const = 0; 92 93 }; 94 95 96 97 /** 98 * KNNSimpleResultSet does not ensure that the element it holds are unique. 99 * Is used in those cases where the nearest neighbour algorithm used does not 100 * attempt to insert the same element multiple times. 101 */ 102 template <typename DistanceType> 103 class KNNSimpleResultSet : public ResultSet<DistanceType> 104 { 105 public: 106 typedef DistanceIndex<DistanceType> DistIndex; 107 KNNSimpleResultSet(size_t capacity_)108 KNNSimpleResultSet(size_t capacity_) : 109 capacity_(capacity_) 110 { 111 // reserving capacity to prevent memory re-allocations 112 dist_index_.resize(capacity_, DistIndex(std::numeric_limits<DistanceType>::max(),-1)); 113 clear(); 114 } 115 ~KNNSimpleResultSet()116 ~KNNSimpleResultSet() 117 { 118 } 119 120 /** 121 * Clears the result set 122 */ clear()123 void clear() 124 { 125 worst_distance_ = std::numeric_limits<DistanceType>::max(); 126 dist_index_[capacity_-1].dist_ = worst_distance_; 127 count_ = 0; 128 } 129 130 /** 131 * 132 * @return Number of elements in the result set 133 */ size()134 size_t size() const 135 { 136 return count_; 137 } 138 139 /** 140 * Radius search result set always reports full 141 * @return 142 */ full()143 bool full() const 144 { 145 return count_==capacity_; 146 } 147 148 /** 149 * Add a point to result set 150 * @param dist distance to point 151 * @param index index of point 152 */ addPoint(DistanceType dist,size_t index)153 void addPoint(DistanceType dist, size_t index) 154 { 155 if (dist>=worst_distance_) return; 156 157 if (count_ < capacity_) ++count_; 158 size_t i; 159 for (i=count_-1; i>0; --i) { 160 #ifdef FLANN_FIRST_MATCH 161 if ( (dist_index_[i-1].dist_>dist) || ((dist==dist_index_[i-1].dist_)&&(dist_index_[i-1].index_>index)) ) 162 #else 163 if (dist_index_[i-1].dist_>dist) 164 #endif 165 { 166 dist_index_[i] = dist_index_[i-1]; 167 } 168 else break; 169 } 170 dist_index_[i].dist_ = dist; 171 dist_index_[i].index_ = index; 172 worst_distance_ = dist_index_[capacity_-1].dist_; 173 } 174 175 /** 176 * Copy indices and distances to output buffers 177 * @param indices 178 * @param dists 179 * @param num_elements Number of elements to copy 180 * @param sorted Indicates if results should be sorted 181 */ 182 void copy(int* indices, DistanceType* dists, size_t num_elements, bool sorted = true) 183 { 184 size_t n = std::min(count_, num_elements); 185 for (size_t i=0; i<n; ++i) { 186 *indices++ = dist_index_[i].index_; 187 *dists++ = dist_index_[i].dist_; 188 } 189 } 190 worstDist()191 DistanceType worstDist() const 192 { 193 return worst_distance_; 194 } 195 196 private: 197 size_t capacity_; 198 size_t count_; 199 DistanceType worst_distance_; 200 std::vector<DistIndex> dist_index_; 201 }; 202 203 /** 204 * K-Nearest neighbour result set. Ensures that the elements inserted are unique 205 */ 206 template <typename DistanceType> 207 class KNNResultSet : public ResultSet<DistanceType> 208 { 209 public: 210 typedef DistanceIndex<DistanceType> DistIndex; 211 KNNResultSet(int capacity)212 KNNResultSet(int capacity) : capacity_(capacity) 213 { 214 // reserving capacity to prevent memory re-allocations 215 dist_index_.resize(capacity_, DistIndex(std::numeric_limits<DistanceType>::max(),-1)); 216 clear(); 217 } 218 ~KNNResultSet()219 ~KNNResultSet() 220 { 221 222 } 223 224 /** 225 * Clears the result set 226 */ clear()227 void clear() 228 { 229 worst_distance_ = std::numeric_limits<DistanceType>::max(); 230 dist_index_[capacity_-1].dist_ = worst_distance_; 231 count_ = 0; 232 } 233 size()234 size_t size() const 235 { 236 return count_; 237 } 238 full()239 bool full() const 240 { 241 return count_ == capacity_; 242 } 243 244 addPoint(DistanceType dist,size_t index)245 void addPoint(DistanceType dist, size_t index) 246 { 247 if (dist >= worst_distance_) return; 248 size_t i; 249 for (i = count_; i > 0; --i) { 250 #ifdef FLANN_FIRST_MATCH 251 if ( (dist_index_[i-1].dist_<=dist) && ((dist!=dist_index_[i-1].dist_)||(dist_index_[i-1].index_<=index)) ) 252 #else 253 if (dist_index_[i-1].dist_<=dist) 254 #endif 255 { 256 // Check for duplicate indices 257 size_t j = i - 1; 258 while (dist_index_[j].dist_ == dist) { 259 if (dist_index_[j].index_ == index) { 260 return; 261 } 262 --j; 263 } 264 break; 265 } 266 } 267 if (count_ < capacity_) ++count_; 268 for (size_t j = count_-1; j > i; --j) { 269 dist_index_[j] = dist_index_[j-1]; 270 } 271 dist_index_[i].dist_ = dist; 272 dist_index_[i].index_ = index; 273 worst_distance_ = dist_index_[capacity_-1].dist_; 274 } 275 276 /** 277 * Copy indices and distances to output buffers 278 * @param indices 279 * @param dists 280 * @param num_elements Number of elements to copy 281 * @param sorted Indicates if results should be sorted 282 */ 283 void copy(int* indices, DistanceType* dists, size_t num_elements, bool sorted = true) 284 { 285 size_t n = std::min(count_, num_elements); 286 for (size_t i=0; i<n; ++i) { 287 *indices++ = dist_index_[i].index_; 288 *dists++ = dist_index_[i].dist_; 289 } 290 } 291 worstDist()292 DistanceType worstDist() const 293 { 294 return worst_distance_; 295 } 296 297 private: 298 size_t capacity_; 299 size_t count_; 300 DistanceType worst_distance_; 301 std::vector<DistIndex> dist_index_; 302 303 }; 304 305 306 307 template <typename DistanceType> 308 class KNNResultSet2 : public ResultSet<DistanceType> 309 { 310 public: 311 typedef DistanceIndex<DistanceType> DistIndex; 312 KNNResultSet2(size_t capacity_)313 KNNResultSet2(size_t capacity_) : 314 capacity_(capacity_) 315 { 316 // reserving capacity to prevent memory re-allocations 317 dist_index_.reserve(capacity_); 318 clear(); 319 } 320 ~KNNResultSet2()321 ~KNNResultSet2() 322 { 323 } 324 325 /** 326 * Clears the result set 327 */ clear()328 void clear() 329 { 330 dist_index_.clear(); 331 worst_dist_ = std::numeric_limits<DistanceType>::max(); 332 is_full_ = false; 333 } 334 335 /** 336 * 337 * @return Number of elements in the result set 338 */ size()339 size_t size() const 340 { 341 return dist_index_.size(); 342 } 343 344 /** 345 * Radius search result set always reports full 346 * @return 347 */ full()348 bool full() const 349 { 350 return is_full_; 351 } 352 353 /** 354 * Add another point to result set 355 * @param dist distance to point 356 * @param index index of point 357 * Pre-conditions: capacity_>0 358 */ addPoint(DistanceType dist,size_t index)359 void addPoint(DistanceType dist, size_t index) 360 { 361 if (dist>=worst_dist_) return; 362 363 if (dist_index_.size()==capacity_) { 364 // if result set if filled to capacity, remove farthest element 365 std::pop_heap(dist_index_.begin(), dist_index_.end()); 366 dist_index_.pop_back(); 367 } 368 369 // add new element 370 dist_index_.push_back(DistIndex(dist,index)); 371 if (is_full_) { // when is_full_==true, we have a heap 372 std::push_heap(dist_index_.begin(), dist_index_.end()); 373 } 374 375 if (dist_index_.size()==capacity_) { 376 if (!is_full_) { 377 std::make_heap(dist_index_.begin(), dist_index_.end()); 378 is_full_ = true; 379 } 380 // we replaced the farthest element, update worst distance 381 worst_dist_ = dist_index_[0].dist_; 382 } 383 } 384 385 /** 386 * Copy indices and distances to output buffers 387 * @param indices 388 * @param dists 389 * @param num_elements Number of elements to copy 390 * @param sorted Indicates if results should be sorted 391 */ 392 void copy(int* indices, DistanceType* dists, size_t num_elements, bool sorted = true) 393 { 394 if (sorted) { 395 // std::sort_heap(dist_index_.begin(), dist_index_.end()); 396 // sort seems faster here, even though dist_index_ is a heap 397 std::sort(dist_index_.begin(), dist_index_.end()); 398 } 399 else { 400 if (num_elements<size()) { 401 std::nth_element(dist_index_.begin(), dist_index_.begin()+num_elements, dist_index_.end()); 402 } 403 } 404 405 size_t n = std::min(dist_index_.size(), num_elements); 406 for (size_t i=0; i<n; ++i) { 407 *indices++ = dist_index_[i].index_; 408 *dists++ = dist_index_[i].dist_; 409 } 410 } 411 worstDist()412 DistanceType worstDist() const 413 { 414 return worst_dist_; 415 } 416 417 private: 418 size_t capacity_; 419 DistanceType worst_dist_; 420 std::vector<DistIndex> dist_index_; 421 bool is_full_; 422 }; 423 424 425 /** 426 * Unbounded radius result set. It will hold as many elements as 427 * are added to it. 428 */ 429 template <typename DistanceType> 430 class RadiusResultSet : public ResultSet<DistanceType> 431 { 432 public: 433 typedef DistanceIndex<DistanceType> DistIndex; 434 RadiusResultSet(DistanceType radius_)435 RadiusResultSet(DistanceType radius_) : 436 radius_(radius_) 437 { 438 // reserving some memory to limit number of re-allocations 439 dist_index_.reserve(1024); 440 clear(); 441 } 442 ~RadiusResultSet()443 ~RadiusResultSet() 444 { 445 } 446 447 /** 448 * Clears the result set 449 */ clear()450 void clear() 451 { 452 dist_index_.clear(); 453 } 454 455 /** 456 * 457 * @return Number of elements in the result set 458 */ size()459 size_t size() const 460 { 461 return dist_index_.size(); 462 } 463 464 /** 465 * Radius search result set always reports full 466 * @return 467 */ full()468 bool full() const 469 { 470 return true; 471 } 472 473 /** 474 * Add another point to result set 475 * @param dist distance to point 476 * @param index index of point 477 * Pre-conditions: capacity_>0 478 */ addPoint(DistanceType dist,size_t index)479 void addPoint(DistanceType dist, size_t index) 480 { 481 if (dist<radius_) { 482 // add new element 483 dist_index_.push_back(DistIndex(dist,index)); 484 } 485 } 486 487 /** 488 * Copy indices and distances to output buffers 489 * @param indices 490 * @param dists 491 * @param num_elements Number of elements to copy 492 * @param sorted Indicates if results should be sorted 493 */ 494 void copy(int* indices, DistanceType* dists, size_t num_elements, bool sorted = true) 495 { 496 if (sorted) { 497 // std::sort_heap(dist_index_.begin(), dist_index_.end()); 498 // sort seems faster here, even though dist_index_ is a heap 499 std::sort(dist_index_.begin(), dist_index_.end()); 500 } 501 else { 502 if (num_elements<size()) { 503 std::nth_element(dist_index_.begin(), dist_index_.begin()+num_elements, dist_index_.end()); 504 } 505 } 506 507 size_t n = std::min(dist_index_.size(), num_elements); 508 for (size_t i=0; i<n; ++i) { 509 *indices++ = dist_index_[i].index_; 510 *dists++ = dist_index_[i].dist_; 511 } 512 } 513 worstDist()514 DistanceType worstDist() const 515 { 516 return radius_; 517 } 518 519 private: 520 DistanceType radius_; 521 std::vector<DistIndex> dist_index_; 522 }; 523 524 525 526 /** 527 * Bounded radius result set. It limits the number of elements 528 * it can hold to a preset capacity. 529 */ 530 template <typename DistanceType> 531 class KNNRadiusResultSet : public ResultSet<DistanceType> 532 { 533 public: 534 typedef DistanceIndex<DistanceType> DistIndex; 535 KNNRadiusResultSet(DistanceType radius_,size_t capacity_)536 KNNRadiusResultSet(DistanceType radius_, size_t capacity_) : 537 radius_(radius_), capacity_(capacity_) 538 { 539 // reserving capacity to prevent memory re-allocations 540 dist_index_.reserve(capacity_); 541 clear(); 542 } 543 ~KNNRadiusResultSet()544 ~KNNRadiusResultSet() 545 { 546 } 547 548 /** 549 * Clears the result set 550 */ clear()551 void clear() 552 { 553 dist_index_.clear(); 554 worst_dist_ = radius_; 555 is_heap_ = false; 556 } 557 558 /** 559 * 560 * @return Number of elements in the result set 561 */ size()562 size_t size() const 563 { 564 return dist_index_.size(); 565 } 566 567 /** 568 * Radius search result set always reports full 569 * @return 570 */ full()571 bool full() const 572 { 573 return true; 574 } 575 576 /** 577 * Add another point to result set 578 * @param dist distance to point 579 * @param index index of point 580 * Pre-conditions: capacity_>0 581 */ addPoint(DistanceType dist,size_t index)582 void addPoint(DistanceType dist, size_t index) 583 { 584 if (dist>=worst_dist_) return; 585 586 if (dist_index_.size()==capacity_) { 587 // if result set is filled to capacity, remove farthest element 588 std::pop_heap(dist_index_.begin(), dist_index_.end()); 589 dist_index_.pop_back(); 590 } 591 592 // add new element 593 dist_index_.push_back(DistIndex(dist,index)); 594 if (is_heap_) { 595 std::push_heap(dist_index_.begin(), dist_index_.end()); 596 } 597 598 if (dist_index_.size()==capacity_) { 599 // when got to full capacity, make it a heap 600 if (!is_heap_) { 601 std::make_heap(dist_index_.begin(), dist_index_.end()); 602 is_heap_ = true; 603 } 604 // we replaced the farthest element, update worst distance 605 worst_dist_ = dist_index_[0].dist_; 606 } 607 } 608 609 /** 610 * Copy indices and distances to output buffers 611 * @param indices 612 * @param dists 613 * @param num_elements Number of elements to copy 614 * @param sorted Indicates if results should be sorted 615 */ 616 void copy(int* indices, DistanceType* dists, size_t num_elements, bool sorted = true) 617 { 618 if (sorted) { 619 // std::sort_heap(dist_index_.begin(), dist_index_.end()); 620 // sort seems faster here, even though dist_index_ is a heap 621 std::sort(dist_index_.begin(), dist_index_.end()); 622 } 623 else { 624 if (num_elements<size()) { 625 std::nth_element(dist_index_.begin(), dist_index_.begin()+num_elements, dist_index_.end()); 626 } 627 } 628 629 size_t n = std::min(dist_index_.size(), num_elements); 630 for (size_t i=0; i<n; ++i) { 631 *indices++ = dist_index_[i].index_; 632 *dists++ = dist_index_[i].dist_; 633 } 634 } 635 worstDist()636 DistanceType worstDist() const 637 { 638 return worst_dist_; 639 } 640 641 private: 642 bool is_heap_; 643 DistanceType radius_; 644 size_t capacity_; 645 DistanceType worst_dist_; 646 std::vector<DistIndex> dist_index_; 647 }; 648 649 650 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 651 /** 652 * This is a result set that only counts the neighbors within a radius. 653 */ 654 655 template <typename DistanceType> 656 class CountRadiusResultSet : public ResultSet<DistanceType> 657 { 658 DistanceType radius; 659 size_t count; 660 661 public: CountRadiusResultSet(DistanceType radius_)662 CountRadiusResultSet(DistanceType radius_ ) : 663 radius(radius_) 664 { 665 clear(); 666 } 667 ~CountRadiusResultSet()668 ~CountRadiusResultSet() 669 { 670 } 671 clear()672 void clear() 673 { 674 count = 0; 675 } 676 size()677 size_t size() const 678 { 679 return count; 680 } 681 full()682 bool full() const 683 { 684 return true; 685 } 686 addPoint(DistanceType dist,size_t index)687 void addPoint(DistanceType dist, size_t index) 688 { 689 if (dist<radius) { 690 count++; 691 } 692 } 693 worstDist()694 DistanceType worstDist() const 695 { 696 return radius; 697 } 698 699 }; 700 701 702 703 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 704 705 /** Class that holds the k NN neighbors 706 */ 707 template<typename DistanceType> 708 class UniqueResultSet : public ResultSet<DistanceType> 709 { 710 public: 711 struct DistIndex 712 { DistIndexDistIndex713 DistIndex(DistanceType dist, unsigned int index) : 714 dist_(dist), index_(index) 715 { 716 } 717 bool operator<(const DistIndex dist_index) const 718 { 719 return (dist_ < dist_index.dist_) || ((dist_ == dist_index.dist_) && index_ < dist_index.index_); 720 } 721 DistanceType dist_; 722 unsigned int index_; 723 }; 724 725 /** Default cosntructor */ UniqueResultSet()726 UniqueResultSet() : 727 worst_distance_(std::numeric_limits<DistanceType>::max()) 728 { 729 } 730 731 /** Check the status of the set 732 * @return true if we have k NN 733 */ full()734 inline bool full() const 735 { 736 return is_full_; 737 } 738 739 /** Remove all elements in the set 740 */ 741 virtual void clear() = 0; 742 743 /** Copy the set to two C arrays 744 * @param indices pointer to a C array of indices 745 * @param dist pointer to a C array of distances 746 * @param n_neighbors the number of neighbors to copy 747 */ 748 virtual void copy(int* indices, DistanceType* dist, int n_neighbors, bool sorted = true) 749 { 750 if (n_neighbors<0) n_neighbors = dist_indices_.size(); 751 int i = 0; 752 typedef typename std::set<DistIndex>::const_iterator Iterator; 753 for (Iterator dist_index = dist_indices_.begin(), dist_index_end = 754 dist_indices_.end(); (dist_index != dist_index_end) && (i < n_neighbors); ++dist_index, ++indices, ++dist, ++i) { 755 *indices = dist_index->index_; 756 *dist = dist_index->dist_; 757 } 758 } 759 760 /** The number of neighbors in the set 761 * @return 762 */ size()763 size_t size() const 764 { 765 return dist_indices_.size(); 766 } 767 768 /** The distance of the furthest neighbor 769 * If we don't have enough neighbors, it returns the max possible value 770 * @return 771 */ worstDist()772 inline DistanceType worstDist() const 773 { 774 return worst_distance_; 775 } 776 protected: 777 /** Flag to say if the set is full */ 778 bool is_full_; 779 780 /** The worst distance found so far */ 781 DistanceType worst_distance_; 782 783 /** The best candidates so far */ 784 std::set<DistIndex> dist_indices_; 785 }; 786 787 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 788 789 /** Class that holds the k NN neighbors 790 * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays 791 */ 792 template<typename DistanceType> 793 class KNNUniqueResultSet : public UniqueResultSet<DistanceType> 794 { 795 public: 796 /** Constructor 797 * @param capacity the number of neighbors to store at max 798 */ KNNUniqueResultSet(unsigned int capacity)799 KNNUniqueResultSet(unsigned int capacity) : capacity_(capacity) 800 { 801 this->is_full_ = false; 802 this->clear(); 803 } 804 805 /** Add a possible candidate to the best neighbors 806 * @param dist distance for that neighbor 807 * @param index index of that neighbor 808 */ addPoint(DistanceType dist,size_t index)809 inline void addPoint(DistanceType dist, size_t index) 810 { 811 // Don't do anything if we are worse than the worst 812 if (dist >= worst_distance_) return; 813 dist_indices_.insert(DistIndex(dist, index)); 814 815 if (is_full_) { 816 if (dist_indices_.size() > capacity_) { 817 dist_indices_.erase(*dist_indices_.rbegin()); 818 worst_distance_ = dist_indices_.rbegin()->dist_; 819 } 820 } 821 else if (dist_indices_.size() == capacity_) { 822 is_full_ = true; 823 worst_distance_ = dist_indices_.rbegin()->dist_; 824 } 825 } 826 827 /** Remove all elements in the set 828 */ clear()829 void clear() 830 { 831 dist_indices_.clear(); 832 worst_distance_ = std::numeric_limits<DistanceType>::max(); 833 is_full_ = false; 834 } 835 836 protected: 837 typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex; 838 using UniqueResultSet<DistanceType>::is_full_; 839 using UniqueResultSet<DistanceType>::worst_distance_; 840 using UniqueResultSet<DistanceType>::dist_indices_; 841 842 /** The number of neighbors to keep */ 843 unsigned int capacity_; 844 }; 845 846 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 847 848 /** Class that holds the radius nearest neighbors 849 * It is more accurate than RadiusResult as it is not limited in the number of neighbors 850 */ 851 template<typename DistanceType> 852 class RadiusUniqueResultSet : public UniqueResultSet<DistanceType> 853 { 854 public: 855 /** Constructor 856 * @param capacity the number of neighbors to store at max 857 */ RadiusUniqueResultSet(DistanceType radius)858 RadiusUniqueResultSet(DistanceType radius) : 859 radius_(radius) 860 { 861 is_full_ = true; 862 } 863 864 /** Add a possible candidate to the best neighbors 865 * @param dist distance for that neighbor 866 * @param index index of that neighbor 867 */ addPoint(DistanceType dist,size_t index)868 void addPoint(DistanceType dist, size_t index) 869 { 870 if (dist < radius_) dist_indices_.insert(DistIndex(dist, index)); 871 } 872 873 /** Remove all elements in the set 874 */ clear()875 inline void clear() 876 { 877 dist_indices_.clear(); 878 } 879 880 881 /** Check the status of the set 882 * @return alwys false 883 */ full()884 inline bool full() const 885 { 886 return true; 887 } 888 889 /** The distance of the furthest neighbor 890 * If we don't have enough neighbors, it returns the max possible value 891 * @return 892 */ worstDist()893 inline DistanceType worstDist() const 894 { 895 return radius_; 896 } 897 private: 898 typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex; 899 using UniqueResultSet<DistanceType>::dist_indices_; 900 using UniqueResultSet<DistanceType>::is_full_; 901 902 /** The furthest distance a neighbor can be */ 903 DistanceType radius_; 904 }; 905 906 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 907 908 /** Class that holds the k NN neighbors within a radius distance 909 */ 910 template<typename DistanceType> 911 class KNNRadiusUniqueResultSet : public KNNUniqueResultSet<DistanceType> 912 { 913 public: 914 /** Constructor 915 * @param capacity the number of neighbors to store at max 916 */ KNNRadiusUniqueResultSet(DistanceType radius,size_t capacity)917 KNNRadiusUniqueResultSet(DistanceType radius, size_t capacity) : KNNUniqueResultSet<DistanceType>(capacity) 918 { 919 this->radius_ = radius; 920 this->clear(); 921 } 922 923 /** Remove all elements in the set 924 */ clear()925 void clear() 926 { 927 dist_indices_.clear(); 928 worst_distance_ = radius_; 929 is_full_ = true; 930 } 931 private: 932 using KNNUniqueResultSet<DistanceType>::dist_indices_; 933 using KNNUniqueResultSet<DistanceType>::is_full_; 934 using KNNUniqueResultSet<DistanceType>::worst_distance_; 935 936 /** The maximum distance of a neighbor */ 937 DistanceType radius_; 938 }; 939 } 940 941 #endif //FLANN_RESULTSET_H 942 943