Jump to content
  • Advertisement
Sign in to follow this  
dnaxx

Efficient data structure for location queries

This topic is 3344 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

Hello, In my settings there are points spread around a 2D plane. Now I want to get the closest of these points to my current location. Which data structure and/or algorithm shows good performance for this operation? The implementation overhead should not be too high (if possible). Regards,

Share this post


Link to post
Share on other sites
Advertisement
You can give the kd-tree a try. It stores the points in a binary search tree. Look here to learn more about the neighbour-search-algorithm using a kd-tree.

Kimmi

Share this post


Link to post
Share on other sites
A regular grid or spatial hash is about the simplest possible thing you could implement, and works quite well when objects are the same size (as they would be with points). The front page had a recent article that might help: http://www.gamedev.net/reference/snippets/features/spatialHash/

Share this post


Link to post
Share on other sites
A hashed grid structure is actually rather difficult to use for NN queries, since it requires a uniform-cost traversal or similar circle-rasterization technique. As kimmi said, kd-trees are ideal for this. Additionally, there's plenty of preexisting kd-tree implementations out there to use.

Share this post


Link to post
Share on other sites
The kd-tree structure has good worst case time performance, but its average case performance is about the same...O(log n). On the other hand, a regular grid has higher memory overhead, but can be tweaked to have average case lookup of nearly O(1) in practice, and is much easier to implement. Depending on your application, this may be significant. When I switched over from kd-tree to uniform grid for 3d spatial indexing of nearest neighbors within a radius, I experienced about a 100-fold speedup in my application.

Share this post


Link to post
Share on other sites
You could store two binary search trees, one for each axis, which map positions on those axes to the points. Take the points to the left and right (in key order) of the sample point "current location" for both the x and y axes. So then you have up to 4 points, one of which is the closest. Return the one with the smallest distance. This approach is O(1), but I doubt it's particularly fast.

Share this post


Link to post
Share on other sites
Quote:
Original post by Baiame
You could store two binary search trees, one for each axis, which map positions on those axes to the points. Take the points to the left and right (in key order) of the sample point "current location" for both the x and y axes. So then you have up to 4 points, one of which is the closest.

That produces incorrect results. Consider the points the five preexisting points (-1,10),(1,10),(10,-1),(10,1), and (2,2), and consider the test point to be (0,0). Your method will return the first four points, when in fact the fifth is the closest.
Quote:
This approach is O(1)
Actually, it's O(log n).

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
That produces incorrect results. Consider the points the five preexisting points (-1,10),(1,10),(10,-1),(10,1), and (2,2), and consider the test point to be (0,0). Your method will return the first four points, when in fact the fifth is the closest.

Aha, right! I couldn't think of a counter-example, but it should've been obvious. The only meaningful information you can actually get out of that algorithm is a box which the real nearest neighbor is either within or on (EDIT- on second thought this is false). Guess you could use it to find potential NNs, though you've highlighted the fatal flaw: the number of worthless points you might get is unbounded.
Quote:
Original post by Sneftel
Actually, it's O(log n).

Why? Finding the l/r elements (twice) is O(1), as is checking the distances, and determining the closest one. So the entire algorithm has to be O(1).

Share this post


Link to post
Share on other sites
Quote:
Original post by Baiame
Quote:
Original post by Sneftel
Quote:
Original post by Sneftel
Actually, it's O(log n).

Why? Finding the l/r elements (twice) is O(1), as is checking the distances, and determining the closest one. So the entire algorithm has to be O(1).
Because a KD-Tree is still a binary tree, which requires log(n) steps down through the tree to reach the leaves.

[Edited by - iMalc on October 16, 2009 1:49:08 PM]

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!