Nanoflann半径搜索

Question

我对search_radiusnanoflann radiusSearch函数中的参数有疑问.我的代码是这样的:

#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

KDTreeEigenMatrixAdaptor 开头的完整定义如下:

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

所以,是的:默认度量是欧氏距离的平方,L2_Adaptor结构,并记录如下:

平方欧几里德距离函子(通用版本,针对高维数据集进行了优化).

至于第二个问题,有两个方面.第一个问题是,在浮点数方面你不应该依赖于平等(强制性参考:David Goldberg,每个计算机科学家应该知道浮点运算,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. (固定半径近邻搜索)给定R ^d中n个不同点的有限集合S 和距离.对于每个点,p∈S报告所有点对(p,q),q∈S,使得从p到q的距离小于或等于.

_{(我最后的重点)}

不过,在数学和计算机科学中,浮点运算问题有效地抑制了对这种严格方式的平等思考.

看来你在这里唯一的选择是略微增加半径,因为CountRadiusResultSet类的使用radiusSearch在FLANN内部的方法实现中是硬编码的.