Incorrect Indices reporting on matrix-wise search

[tsandy]

Hello, There seems to be a small bug in knn for matrix-type queries. Non-zero indices are reported even when dists2 returns 'inf'. See the code snippet and output below. Best, Tim

Code--------------------------------------------------

#include "nabo/nabo.h"
#include <Eigen/Core>
#include <iostream>

int main(int argc, char** argv)
{
    Eigen::MatrixXd M = Eigen::MatrixXd::Random(3, 10);
    /*Eigen::MatrixXd M(3,10);
    M.setOnes();
    M(0,0) = 0.1;
    M(0,1) = 0.1;
    M(0,2) = 0.1;*/

    Nabo::NNSearchD* nns = Nabo::NNSearchD::createKDTreeLinearHeap(M);

    Eigen::MatrixXd dists2(5,10);
    Eigen::MatrixXi indices(5,10);
    nns->knn(M, indices, dists2, 5, 0, 0, 1.0);

    std::cout << "Points:" << std::endl;
    std::cout << M << std::endl;
    std::cout << "Indices:" << std::endl;
    std::cout << indices << std::endl;
    std::cout << "Dists:" << std::endl;
    std::cout << dists2 << std::endl;
}

Output----------------------------------------

Points:
  0.680375    0.59688  -0.329554    0.10794  -0.270431    0.83239  -0.716795  -0.514226  -0.686642  -0.782382
 -0.211234   0.823295   0.536459 -0.0452059  0.0268018   0.271423   0.213938  -0.725537  -0.198111   0.997849
  0.566198  -0.604897  -0.444451   0.257742   0.904459   0.434594  -0.967399   0.608354  -0.740419  -0.563486
Indices:
5 2 9 0 3 0 8 4 6 2
3 5 6 4 7 3 2 3 2 6
0 3 8 5 0 3 9 8 4 6
0 0 1 7 4 7 0 2 3 2
0 0 2 9 5 0 3 9 8 4
Dists:
0.273387 0.966299 0.432103 0.450393 0.566593 0.273387 0.222213 0.713128 0.222213 0.432103
0.450393      inf  0.52745 0.566593 0.713128 0.656359  0.52745  0.97287 0.754702 0.781964
     inf      inf 0.754702 0.656359      inf      inf 0.781964      inf      inf      inf
     inf      inf 0.966299  0.97287      inf      inf      inf      inf      inf      inf
     inf      inf      inf      inf      inf      inf      inf      inf      inf      inf

[simonlynen]

@tsandy Thank you for the detailed report. Yes this is a known behavior of the library in that the indices are not reset for points exceeding the distance threshold. You will need to evaluate the distance in order to see if a point is valid.

We have taken the decision to not have a dedicated index for invalid points: See https://github.com/ethz-asl/libnabo/issues/2 for a discussion.

[stephanemagnenat]

The documentation (nabo.h:318 for instance) states that the indices will be filled with zero, and therefore is wrong, so we should update it.

[simonlynen]

@stephanemagnenat please take a look at #24

Points:
 -0.999984 -0.0826997  -0.905911   0.869386   0.661931  0.0594004  -0.233169   0.373545   0.692334   0.307838
 -0.736924  0.0655345   0.357729  -0.232996  -0.930856   0.342299  -0.866316   0.177953  0.0538576  -0.168001
  0.511211  -0.562082   0.358593  0.0388327  -0.893077  -0.984604  -0.165028   0.860873   -0.81607   0.402381
Indices:
0 5 0 9 8 1 0 9 5 7
0 8 0 8 0 8 0 0 1 3
0 0 0 0 0 0 0 0 3 0
0 0 0 0 0 0 0 0 4 0
0 0 0 0 0 0 0 0 0 0
Dists:
     inf 0.275316      inf 0.451728 0.976515 0.275316      inf 0.334217 0.512207 0.334217
     inf 0.665324      inf 0.844491      inf 0.512207      inf      inf 0.665324 0.451728
     inf      inf      inf      inf      inf      inf      inf      inf 0.844491      inf
     inf      inf      inf      inf      inf      inf      inf      inf 0.976515      inf
     inf      inf      inf      inf      inf      inf      inf      inf      inf      inf

[stephanemagnenat]

Looks good to me

[tsandy]

Thanks for the quick replies!