I am looking for a library that implements nearest-neighbour search in 2D and provides either k nearest neighbour or all neighbours within a given distance. I like
because it works for any dimension. However, it does not seem to have a lot of clients - so maybe there is something else that I should at least consider?
Hello @lindig,
There is a library, bst. It’s not exactly the VP-tree (Vantage-Point Tree) method, but rather a bisector tree. However, I believe it could be used for K-NN searches if a distance metric is provided, although I have never explored whether it includes a ready-to-use K-NN function.
not exactly what you are looking for, but not too far: my Path library
(oplot/lib/path.ml at master · sanette/oplot · GitHub) implements “joining paths whose endpoints are close”; Hence there is a search for epsilon-close neighbors in 2D.
it is quite fast because in 2D you can set up a grid of size epsilon and only search in the 8 neighbouring cells for each point. Hence the algo is O(N)