Jump to content
  • Advertisement
Sign in to follow this  
StubbornDuck

Fixed-radius near neighbor search

This topic is 2079 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I need to find all points within a given radius of a certain point in euclidean 2D and 3D spaces. The points are updated fairly often (but most commonly are just moved by a limited distance). The point distributions are likely to be very non-uniform in my application. There's a limit to the resolution I need, I'd rather trade resolution for performance (at least if I can over-estimate rather than under-estimate returned point sets).

 

I know I could use spatial hashed grids or quad/octrees for this. Unfortunately the Wikipedia article for fixed-radius near neighbor search is a stub, and googling gives me very specific results rather than an overview, so my quick rush to gain an overview ended there. ^^ I wonder if someone else has a better idea than spatial grids or oct/quadtrees - if you can give me names of algorithm/data structures that work in your experience, that will save me a couple of hours and I will be very happy.

 

Edit: Oh and if the data struture can be updated concurrently it's a plus.

Edited by Petter Hansson

Share this post


Link to post
Share on other sites
Advertisement
I don't quite get if your problem is that you don't understand the solution using oct/quadtrees because you haven't found a good description, or if there is something wrong with that solution for your particular situation. Can you clarify?

Share this post


Link to post
Share on other sites

I haven't written any code yet (for the search, the application already exists). I understand quad/octrees, but I doubt they're the best option given the number of updates I will be doing from multiple concurrent tasks. Let's say the application is "air traffic control" for illustrative purposes (not really true as the objects will be clustering up more than aircraft).

 

I will use spatial hashes as a baseline I think, as I suspect they will perform comparatively well and are easy to implement. Then I'll see if any other solutions I try outperform it.

Edited by Petter Hansson

Share this post


Link to post
Share on other sites
Look into B-Trees and in particular the B+ Tree. You should be able to create a spatially specific strategy for the generation/selection of sub nodes that is fairly efficient for nearest neighbor problems with adaptive data. If you are willing to do a little more theory work the Z-order looks really interesting and I suspect it could be quite fast for this class of problem.

Hope this helps.

Share this post


Link to post
Share on other sites
I don't understand your concern with trading off "resolution" and "performance". In an adaptive data structure like a quadtree there's a point at which the bookkeeping of further subdivision of a cell costs more than the explicit distance evaluations it saves, but this cutoff doesn't depends on the size of the cell, but rather on the number of objects in the cell and the fraction of these objects that could be rejected with finer subdivision.

Share this post


Link to post
Share on other sites

That concern wasn't for quadtrees specifically, rather it was for any other algorithms proposed for which it might be applicable. But I thank both you and Alvaro for stating your confusion, it means I will try to be more clear next time. I'm not as mathematically minded as I wish I were, unfortunately, so I sometimes come off as logically incoherent in the finer details.

Edited by Petter Hansson

Share this post


Link to post
Share on other sites

And, well, kd-trees are nice too, and work fairly well in 2D and 3D space. You're looking for a range kNN search (you can also find the k nearest neighbours irrespective of range, but there is an efficient algorithm for range searching). kd-trees adapt to your dataset so they would likely be better for highly non-uniform distributions, but it's really hard to tell whether there would be any difference for your particular datasets.

 

Also, there are variants for approximate range searching (to arbitrary precision, trading off quality for speed) but I haven't tried them personally. And I'm sure they also exist for quad-trees.

Share this post


Link to post
Share on other sites

You might also look into an R tree. If you're doing a lot of modifications to the structure at run time, an R tree will outperform a kd tree. A bit more complex though.

Share this post


Link to post
Share on other sites

Thanks for both suggestions. Thought KD trees were slow to update but maybe it will work. Like you note, it's hard to tell what will work best in practice so I'll have to try a couple of different solutions.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!