Nanoflann半徑搜索

Question

我對nanoflann的radiusSearch函數中的參數search_radius有疑問。我的代碼是這樣的：

#include <iostream> 
#include <vector> 
#include <map> 

#include "nanoflann.hpp" 
#include "Eigen/Dense" 

int main() 
{ 
    Eigen::MatrixXf mat(7, 2); 
    mat(0,0) = 0.0; mat(0,1) = 0.0; 
    mat(1,0) = 0.1; mat(1,1) = 0.0; 
    mat(2,0) = -0.1; mat(2,1) = 0.0; 
    mat(3,0) = 0.2; mat(3,1) = 0.0; 
    mat(4,0) = -0.2; mat(4,1) = 0.0; 
    mat(5,0) = 0.5; mat(5,1) = 0.0; 
    mat(6,0) = -0.5; mat(6,1) = 0.0; 

    std::vector<float> query_pt(2); 
    query_pt[0] = 0.0; 
    query_pt[1] = 0.0; 

    typedef nanoflann::KDTreeEigenMatrixAdaptor<Eigen::MatrixXf> KDTree; 

    KDTree index(2, mat, 10); 
    index.index->buildIndex(); 

    { // Find nearest neighbors in radius 
     const float search_radius = 0.1f; 
     std::vector<std::pair<size_t, float> > matches; 

     nanoflann::SearchParams params; 

     const size_t nMatches = index.index->radiusSearch(&query_pt[0], search_radius, matches, params); 

     std::cout << "RadiusSearch(): radius = " << search_radius << " -> " 
        << nMatches << " matches" << std::endl; 
     for(size_t i = 0; i < nMatches; i++) 
      std::cout << "Idx[" << i << "] = " << matches[i].first 
         << " dist[" << i << "] = " << matches[i].second << std::endl; 
     std::cout << std::endl; 
    } 
} 

我想是的0.1半徑範圍內都有分點，所以，我的預期是在基體中，但讓我吃驚的前三個元素，它返回第5元素。檢查距離返回它似乎不是實際的距離，但距離平方（右？），所以我平方半徑得到我的預期，但不幸的是它只返回第一點。

所以我增加了一點點半徑從0.1^2 = 0.01到0.02終於得到了我想要的點。

現在的問題是，不應該把鄰里周邊的點包括在內嗎？我在哪裏可以在nanoflann中更改這種情況？

Answer 1

的KDTreeEigenMatrixAdaptorstarts like this完整定義：

template <class MatrixType, int DIM = -1, 
      class Distance = nanoflann::metric_L2, 
      typename IndexType = size_t> 
struct KDTreeEigenMatrixAdaptor 
{ 
//... 

所以，是的：默認度量是平方歐氏距離，L2_Adaptor結構，and documented as follows：

歐氏距離平方算符（通用版，針對高維數據集進行了優化）。

至於第二個問題，有兩個方面。首先，浮點數不應該依賴平等（強制性參考：David Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys, 1991）。

其次，原則上，你是對的。 nanoflann基於FLANN，其中的源代碼可以找到CountRadiusResultSet類的實現，由radiusSearch搜索方法使用。其關鍵方法具有以下實現：

void addPoint(DistanceType dist, size_t index) 
{ 
    if (dist<radius) { 
     count++; 
    } 
} 

儘管看來此問題的一個共同的定義涉及「小於或等於」，如例如在以下參考文獻（Matthew T. Dickerson, David Eppstein, Algorithms for Proximity Problems in Higher Dimensions, Computational Geometry, 1996）：

問題1：（固定半徑近鄰搜索）給定一個有限集合S中的n個不同的點在R ^d和一個距離。對於每個點p∈S報告所有點對（p，q），q∈S，使得從p到q的距離爲小於或等於。

_{（最後強調由我）}

不過，這是數學和計算機科學的浮點運算問題，有效地抑制在如此嚴格的方式思考平等。

看來你在這裏的唯一選擇是稍微增加半徑，因爲CountRadiusResultSet類的使用在FLANN中的radiusSearch方法實現中被硬編碼。