What is the quickest way to find the shortest cart

Question

I have 1 red polygon say and 50 randomly placed blue polygons - they are situated in geographical 2D space. What is the quickest/speediest algorithim to find the the shortest distance between a red polygon and its nearest blue polygon?

Bear in mind that it is not a simple case of taking the points that make up the vertices of the polygon as values to test for distance as they may not necessarily be the closest points.

So in the end - the answer should give back the closest blue polygon to the singular red one.

This is harder than it sounds!

Answer 1

I believe what you are looking for is the A* algorithm, its used in pathfinding.

Answer 2

Gotta run off to a funeral in a sec, but if you break your polygons down into convex subpolies, there are some optimizations you can do. You can do a binary searches on each poly to find the closest vertex, and then I believe the closest point should either be that vertex, or an adjacent edge. This means you should be able to do it in log(log m * n) where m is the average number of vertices on a poly, and n is the number of polies. This is kind of hastey, so it could be wrong. Will give more details later if wanted.

Answer 3

I would start by bounding all the polygons by a bounding circle and then finding an upper bound of the minimal distance. Then i would simply check the edges of all blue polygons whose lower bound of distance is lower than the upper bound of minimal distance against all the edges of the red polygon.

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

But it all depends on your data. If the blue polygons are relatively small compared to the distances between them and the red polygon, then this approach should work nicely, but if they are very close, you won't save anything (many of them will be close enough). And another thing -- If these polygons don't have many vertices (like if most of them were triangles), then it might be almost as fast to just check each red edge against each blue edge.

hope it helps

Answer 4

I doubt there is better solution than calculating the distance between the red one and every blue one and sorting these by length.

Regarding sorting, usually QuickSort is hard to beat in performance (an optimized one, that cuts off recursion if size goes below 7 items and switches to something like InsertionSort, maybe ShellSort).

Thus I guess the question is how to quickly calculate the distance between two polygons, after all you need to make this computation 50 times.

The following approach will work for 3D as well, but is probably not the fastest one:

Minimum Polygon Distance in 2D Space

The question is, are you willing to trade accuracy for speed? E.g. you can pack all polygons into bounding boxes, where the sides of the boxes are parallel to the coordinate system axes. 3D games use this approach pretty often. Therefor you need to find the maximum and minimum values for every coordinate (x, y, z) to construct the virtual bounding box. Calculating the distances of these bounding boxes is then a pretty trivial task.

Here's an example image of more advanced bounding boxes, that are not parallel to the coordinate system axes:

Oriented Bounding Boxes - OBB

However, this makes the distance calculation less trivial. It is used for collision detection, as you don't need to know the distance for that, you only need to know if one edge of one bounding box lies within another bounding box.

The following image shows an axes aligned bounding box:

Axes Aligned Bounding Box - AABB

OOBs are more accurate, AABBs are faster. Maybe you'd like to read this article:

Advanced Collision Detection Techniques

This is always assuming, that you are willing to trade precision for speed. If precision is more important than speed, you may need a more advanced technique.

Answer 5

I know you said "the shortest distance" but you really meant the optimal solution or a "good/very good" solution is fine for your problem?

Because if you need to find the optimal solution, you have to calculate the distance between all of your source and destination poligon bounds (not only vertexes). If you are in 3D space then each bound is a plane. That can be a big problem (O(n^2)) depending on how many vertexes you have.

So if you have vertex count that makes that squares to a scarry number AND a "good/very good" solution is fine for you, go for a heuristic solution or approximation.

Answer 6

For polygon shapes with a reasonable number of boundary points such as in a GIS or games application it might be quicker easier to do a series of tests.

For each vertex in the red polygon compute the distance to each vertex in the blue polygons and find the closest (hint, compare distance^2 so you don't need the sqrt() ) Find the closest, then check the vertex on each side of the found red and blue vertex to decide which line segments are closest and then find the closest approach between two line segments.

See http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/ (it's easy to simply for the 2d case)