# Nearest Point

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

## 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 on other sites
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 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 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 on other sites
Check out Octree's (which is the term for the ideas above)!

You can get a big speed boost using this!

##### 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 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 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).

1. 1
Rutin
48
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 11
• 16
• 9
• 10
• 13
• ### Forum Statistics

• Total Topics
633003
• Total Posts
3009846
• ### Who's Online (See full list)

There are no registered users currently online

×