BRabbit27 -4 years ago 103

C++ Question

I have a doubt regarding the parameter

`search_radius`

`radiusSearch`

`#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

So I increased a little bit the radius from

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?

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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 R^{d}and a distance

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

Latest added