Nanoflann radius search

Question

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?

Abampere

Answer 1

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 R^d and a distance 𝛿. For each point p ∈ S report all pairs of points (p,q), q ∈ S such that the distance from p to q is less than or equal to 𝛿.

_{(the last emphasis by me)}

Still, that's mathematics and in Computer Science the floating-point arithmetic problems effectively inhibit thinking about equality in such a strict manner.

It seems that your only choice here is to slightly increase the radius, because the usage of the CountRadiusResultSet class is hard-coded in radiusSearch method implementation inside FLANN.

Pomeroy

Ok thanks for a very complete description. I definitely have to read that paper about floating-point arithmetic. Just one more question, isn't L2_Norm defined as sqrt(dot(v,v)) ... I guess they just kept it as dot(v,v) in nanoflann, is it? – Abampere

@Abampere Yes, the name is misleading. – Pomeroy