What is the quickest way to find the shortest cartesian distance between two polygons

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!

Solution 1

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.

Solution 2

You might be able to reduce the problem, and then do an intensive search on a small set.

Process each polygon first by finding:

• Center of polygon
• Maximum radius of polygon (i.e., point on edge/surface/vertex of the polygon furthest from the defined center)

Now you can collect, say, the 5-10 closest polygons to the red one (find the distance center to center, subtract the radius, sort the list and take the top 5) and then do a much more exhaustive routine.

Solution 3

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)

Solution 4

Maybe the Frechet Distance is what your looking for?

Computing the Fréchet distance between two polygonal curves
Computing the Fréchet Distance Between Simple Polygons

Solution 5

This screening technique is intended to reduce the number of distance computations you need to perform in the average case, without compromising the accuracy of the result. It works on convex and concave polygons.

Find the the minimum distance between each pair of vertexes such that one is a red vertex and one is a blue. Call it r. The distance between the polygons is at most r. Construct a new region from the red polygon where each line segment is moved outward by r and is joined to its neighbors by an arc of radius r is centered at the vertex. Find the distance from each vertex inside this region to every line segment of the opposite color that intersects this region.

Of course you could add an approximate method such as bounding boxes to quickly determine which of the blue polygons can't possibly intersect with the red region.

View more solutions

Comments

[Vidar]

Hi - I have already done something similiar to what you have said - but it does take a while, especially with large polygons. But thanks.

[Mike Tunnicliffe]

I'm envisioning some weirdly shaped polygon that could have its centre far away but vertices a lot nearer than the closest 5 or 10 polygons. Depending on your constraints this could be an acceptable optimisation though.

[brady]

If by "point" you mean "vertex", it won't give you the correct result either.

[Adam Davis]

That should be taken care of - the maximum distance from the center to any given vertex becomes the polygon's radius, and that is used to determine closeness, not the center.

[danio]

Shamos' Rotating calipers technique ("Minimum Polygon Distance in 2D Space") only works for convex polygons.

[SimonHawkins]

Bounding circles will establish a minimum distance between the red and any blue. Starting with the closest pair, establish their precise distance using rotating calipers or some other method. With that seed distance, you only need to examine other polygon pairs that are less than that distance between the edges of their bounding circles.

[Vidar]

That's a crucuial point @danio - for a complete and accurate algorithm - it should take into account convex and concave polygons.

[Martijn Pieters]

Answers which just contain links are considered bad practice. Please summarize the content here (don't copy/paste) so the answer can stand on its own. If you don't you run the risk of your answer being removed, especially if the links ever die (again).