Finding the Nanofland radius

I have a doubt about a parameter search_radius

in a nanofland function radiusSearch

. My code:

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

    {   // 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;


I want to have points in a radius of 0.1 , so I expected these to be the first three elements in the matrix, but to my surprise, it returned the first 5 elements. The fidelity check seems to me that it is not the actual distance, but the square of the distance (right?), So I square the radius to get what I expected, but unfortunately it only returns the first point.

So, I increased the radius slightly from 0.1 ^ 2 = 0.01 to 0.02 and finally got the points I needed.

Now the question is, should the points lying on the perimeter of the neighborhood be included? Where can I change this condition in the nanoflan?


source to share

1 answer

The full definition KDTreeEigenMatrixAdaptor

begins as follows:

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, structure L2_Adaptor

, and is documented as follows :

Quadratic Euclidean distance functor (generic version optimized for high-dimensional datasets).

As for the second question, there are two aspects. First, you shouldn't rely on equality when it comes to floating point numbers (required reference: David Goldberg, What Every Computer Scientist Should Know About Floating Point Arithmetic, ACM Computing Surveys, 1991).

Second, you are basically right. Nanofland is based on FLANN, where you can find the source code in the class CountRadiusResultSet

used by the search method radiusSearch

. Its key method has the following implementation:

void addPoint(DistanceType dist, size_t index)
    if (dist<radius) {


While the general definition of this problem seems to include "less than or equal", such as in the following link ( Matthew T. Dickerson, David Eppstein, Algorithms for Proximity Problems in Higher Dimensions, Computational Geometry, 1996) :

Problem 1. (search with a fixed radius of the nearest neighbors) . For a finite set S of n different points in R d and a, the distance δ. For each point p ∈ S, all pairs of points (p, q), q ∈ S, for which the distance from p to q is less than or equal to δ is reported .

(last highlight by me)

However, this mathematics and computer science floating point arithmetic problems effectively discourage thinking about equality in such a strict manner.

It seems that your only choice here is to increase the radius slightly because the use of the class is CountRadiusResultSet

hardcoded in the method implementation radiusSearch

inside FLANN.



All Articles