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);
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;
}
}
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
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) {
count++;
}
}
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.
source to share