Jump to content
  • Advertisement
Sign in to follow this  
JasonHise

Nearest Point

This topic is 4219 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 have a fixed set of 2^16 points located inside a unit cube in 3-space. I need to be able to detect which of these is closest to a new random point very frequently and very quickly. A linear search through all of the fixed points is too slow, so I want to organize the fixed points into some sort of rapidly traversable graph. In looking online, it appears that the best structure would be a Delaunay triangulation. However, the listed algorithmic information doesn't seem complete enough to help me know how to generate this graph. Any suggestions?

Share this post


Link to post
Share on other sites
Advertisement
I think what you really want is a Voronoi diagram (related to Delaunay triangulation), which will give you the set of convex regions. Then for fast lookup, you could then organize those regions into a BSP tree.

Share this post


Link to post
Share on other sites
A quick-n-dirty solution(not optimal) would be to just divide the cubes into smaller cubes, like a 3D grid. Each subcube will have a coordinate, let's say (cx,cy,cz). Each of these 2^16 points belongs only to 1 subcube. This simplifies things. Given a new point(x,y,z), it's very easy to determine in which subcube(cx,cy,cz) it belongs. From there on, you just search for the nearest point only in that subcube, and ignore all the rest. In the (unlikely) possibility that a subcube is completely empty, you can flag it as such and so you don't search in it for nearest points, but in its neighbours. A hierarchical structure(like an octree) instead of a grid would be better.

Share this post


Link to post
Share on other sites
A Voronoi diagram would work, but again I don't know how to generate it. In that case it seems like I need an efficient way to test for redundant linear constraints so that I could prune the majority of the bounding planes surrounding each point. But I can't think of any algorithm to manage this which wouldn't be prohibitively expensive.

Share this post


Link to post
Share on other sites
mikeman has the right idea. It's sometimes called the Spanish Moss or Hanging Moss algorithm. It's incredibly simple and straightforward, far easier to update in real-time (if your points are moving) than other silly structures, has consistent performance across the space (unlike the death planes of quad/oct-trees), etc... Seriously, don't overcomplicate this.

Pick a good resolution, and partition all your points into a uniform grid. Given a new point, it's O(1) to decide which grid cell it lies in. Test against all points in that cell and each of it's neighbors (because of edge cases). Technically, you need to spiral out if there are no nearby points.

Share this post


Link to post
Share on other sites
With regard to the hanging moss algorithm...

To be completely honest, the positions of the fixed points aren't totally random... they will always be along a line connecting two of 16 special points. These 16 special points exist at the corners of a cube stretching from <0,0,0> to <1, 1, 1>, the corners of a cube stretching from <0,0,0> to <0.5, 0.5, 0.5> (minus the redundant origin point), and the point at <0.75, 0.75, 0.75>. While this creates a decent spiderweb, there are still a fair number of gaps and clusters. Hence spiraling will happen frequently, and the number of points which will need to be searched will grow rapidly as more lines intersect the search space.

I think that using an octree may help to mitigate the clustering problem, but I'm left with the problem that I don't know how to test edge cases with an octree.

Share this post


Link to post
Share on other sites
This problem is called a nearest neighbor search. You could use an octree or a kd-tree or a similiar type of tree. First you use the tree to quickly find the node that contains the query point and find the point associated with that node that is closest to the query point. Now you have an upper bound on the distance between the query point and the closest point. That gives you a sphere you can use to cull nodes as you search for the closest point (and if you come across any points that are even closer you use them instead and get an even tighter upper bound).

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!