Adding a previously removed index results in unexpected behavior.

[YashBansod]

I tried to add the removed index at https://github.com/jlblancoc/nanoflann/blob/4c47ca200209550c5628c89803591f8a753c8181/examples/dynamic_pointcloud_example.cpp#L69-L70 by adding the following code:

cloud.pts[N-1] = { 0.5, 0.5, 0.5 };
cout << "N-1 point: (" << cloud.pts[N-1].x << ", " << cloud.pts[N-1].y << ", " << cloud.pts[N-1].z << ")" << endl;
index.addPoints(N-1, N-1);

This should result in the closest point at (0.5, 0.5, 0.5) with a distance value of 0. However, the code results in a different value (based on the original random closest point).

This behavior only happens if I try to re-add a previously removed index. Can someone explain why this is happening? Is this a Bug?

[jlblancoc]

It seems so. Thanks for reporting, we'll try to address it, or if in the meanwhile you find a patch, PRs are welcome! ;-)

[Pikecillo]

The problem is that treeIndex[N-1] is not being updated on the re-add of the point after being set to -1 during the deletion.

A fix draft can be found in this PR https://github.com/jlblancoc/nanoflann/pull/172

Thoughts on two points are welcomed (please comments on PR):

1. treeIndex is now a hash map instead of a vector, so it's expected to be slower. A vector<bool> could be used instead of a hashmap to alleviate this but depending on how points are loaded in the index this may mean extra space. does any other alternative comes to mind folks?
2. The semantic of the argument void removePoint(size_t idx) changed. Previously that index referred to the order in which points were added to the set, now it's the same index space as the arguments of function void addPoints(AccessorType start, AccessorType end) (in other words, previously if the first bunch of points added are addPoints(100, 200), and I wanted to delete point with index 100, I would have to do remove(0), currently I have to do remove(100) )

[jlblancoc]

Oh, I saw this after the PR :-) Ok, further comments on the PR.