BRabbit27 BRabbit27 -4 years ago 103
C++ Question

Nanoflann radius search

I have a doubt regarding the parameter

search_radius
in nanoflann's
radiusSearch
function. My code is this:

#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;
}
}


What I want is to have the points within a radius of 0.1, so, what I expected was the first three elements in the matrix but to my surprise it returned the first 5 elements. Checking the distances return it seems to me that it is not the actual distance but the distance-squared (right?) so I squared the radius to get what I expected but unfortunately it returns only the first point.

So I increased a little bit the radius from 0.1^2 = 0.01 to 0.02 and finally got the points I wanted.

Now, the question is, shouldn't the points laying on the perimeter of the neighborhood be included? Where can I change this condition in nanoflann?

Answer Source

The full definition of KDTreeEigenMatrixAdaptor starts like this:

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

So, yes: the default metric is the squared Euclidean distance, the L2_Adaptor struct, and documented as follows:

Squared Euclidean distance functor (generic version, optimized for high-dimensionality data sets).

As for the second issue, there are two aspects. First one is that you should not rely on equality when it comes to floating point numbers (obligatory reference: David Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys, 1991).

Second is that in principle, you are right. nanoflann is based on FLANN, in which's source code you may find the implementation of CountRadiusResultSet class, used by the radiusSearch search method. Its key method has the following implementation:

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

Whereas it seems that a common definition of this problem involves "less than or equal", as for example in the following reference (Matthew T. Dickerson, David Eppstein, Algorithms for Proximity Problems in Higher Dimensions, Computational Geometry, 1996):

Problem 1. (Fixed-Radius Near-Neighbors Search) Given a finite set S of n distinct points in Rd and a distance

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download