search

BrunoLevy / geogram

a programming library with geometric algorithms
Other
1.87k stars 126 forks source link

Potential bug with nearest neighbor search? #190

Closed jmag722 closed 1 day ago

jmag722 commented 1 week ago

Hello! I'm running into issues with the nn_search library. When I try to query a single point with get_nearest_neighbor, I often get the correct answer, but for some combinations of inputs I get the wrong index back out. Often the index can exceed the index values of the coordinate inputs, causing an out of bounds error if I try to use that returned index elsewhere.

I have a demonstration case at https://github.com/jmag722/geogram_nn_bug. As-is, the C++ code outputs an index of 9. I also have a python script that uses scipy to output the expected answer (4). I've experimented with adding an additional point to the initial vector coordinates to change the answer.

The wildest thing is that when I comment out the values vector or even just its first value, that changes the answer I get from get_nearest_neighbor later! But values isn't even used in the code! Maybe something weird with my compilation but I'm not sure what it could be. It could very well be this is all on my end though or something with my setup.

BrunoLevy commented 1 week ago

Hello, Thank you very much for this detailed problem report ! (love it when there is a minimal example as you did) I'll take a look and come back to you. On which platform was it ? (Windows/mac/unix ?)

jmag722 commented 6 days ago

You're welcome! It's Linux (Mint), further details below on my setup:

# uname -a
Linux jared-MS-7D93 6.8.0-48-generic #48-Ubuntu SMP PREEMPT_DYNAMIC Fri Sep 27 14:04:52 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux
# g++ --version
g++ (Ubuntu 13.2.0-23ubuntu4) 13.2.0
# cmake --version
cmake version 3.28.3
BrunoLevy commented 1 day ago

Found out !

Replace

interp->set_points(coords.size(), coords.data());

with

interp->set_points(coords.size()/2, coords.data());

(first parameter of set_points() is number of points, not total number of coordinates)