CODEWITHSUNDEEP
c++data-structuresspatialknnnearest-neighbor
ameya.dubey
ameya.dubey

Reputation: 85

Spatial querying for k-th closest neighbour of a point

I'm working on an algorithm that repeatedly needs the (Euclidean) distance to the k-th closest point from some given query point all taken from a vector of points. Also, I repeatedly need to find all points within a given radius of a point.

I'm thinking of using k-d trees from the nanoflann library. However, the knnSearch() function returns all the k nearest neighbours, which I don't require. (The radiusSearch() function suits me just fine, though).

Is there a more efficient way to get what I need, other than slogging through all the k nearest neighbours every time? A better data structure or a better implementation? (I'm using C++.)

Upvotes: 1

Views: 790

Answers (1)

gsamaras
gsamaras

Reputation: 73366

I'm thinking of using k-d trees

Excellent choice for 2D or 3D.

k-d trees are a good choice for low dimensional data (which I assume you have since nanoflann is "mostly optimized for 2D or 3D point clouds.").

Is there a more efficient way to get what I need, other than slogging through all the k nearest neighbors every time?

You need the k-th Nearest Neighbor (NN), but when searching a k-d tree for k NNs, the costly operation (in terms of time) is finding the first NN (which requires you to descend down the tree, all way from the root to a leaf).

Finding the 2nd, 3rd or another indexed NN is relatively cheap, and I highly doubt that it will harm performance (i.e. that getting the k-th NN out of the k NNs returned by the tree will be the bottleneck).

So, I strongly suggest you not to worry about that step.

A better data structure or a better implementation?

I don't think so. I haven't used nanoflann, but CGAL for this kind of queries, and it worth giving a try (however CGAL requires installing (not a piece of cake), while nanoflann is just a header include).

Upvotes: 1

Related Questions