Feature request about NN search strategy.

[xlicz]

There are two types of NNS query: the k-NN search and the fixed radius search. The combination of the two types yields the ranged search, i.e. the retrieval of the k NN with a given maximal distance.

According to a paper ETH published in 2012[1], it's beneficial to implement this kind of search variant in the context of point cloud registration. It's reasonable as we are only interested in those points whose distance are within a prior range to get right ICP result. As a result, we reduce the search space and get better performance.

They have implemented this search variant in libnabo.

How do you think about this feature?

[1] Elseberg, J., Magnenat, S., Siegwart, R., & Andreas, N. (2012). Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration. Journal of Software Engineering for Robotics (JOSER), 3(1), 2–12.

[nitro44x]

I am also interested in this feature. We currently pay the cost of two searchs (k-NN to find the min required radius, followed by a radius search). It is less than optimal, and we haven't profiled enough to tell if its a real bottleneck for our case yet.

+1

[jdumas]

+1 for this feature request. It looks like this could be achieved by using findNeighbors() directly with a slightly modified KNNResultSet, where worstDist is set by the user (as in RadiusResultSet).

[lewisjiang]

+1

After reading the code, I adopt a simple workaround:
nanoflann uses the last element of KNNResultSet::dists_[capacity-1] as worstDist() to prune leaf nodes and sub nodes in the backbone search function XXXAdaptor::searchLevel(), and this dists_[capacity-1] is initialized to the max possible value in KNNResultSet::init(). So you can manually set it in init(), and check the search results in case less than capacity are valid.