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?
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 ๐ฟ. 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With