Distance between two convex polygons in 3D

Question

I have two convex polygons in 3D. They are both flat on different planes, so they're a pair of faces.

What's the simplest way to calculate the closest distance between these two polygons?

Edit: The length of the shortest possible line that has an endpoint in the first polygon and another other endpoint in the second polygon. The distance that I'm looking for is the length of this shortest possible line.

Answer 1

Well, there are only a few possibilities; the shortest line between the two polygons could be:

1. Between two vertices
2. Between an edge and a vertex
3. Between two edges (imagine two polygons on perpendicular planes)
4. Between a vertex and the inside of the polygon
5. Or the polygons intersect

Cases 1-3 are all taken care of by treating each edge + vertex-pair as a line segment, and enumerating the distance between all line-segment pairs.

For case 4, find the distance between each vertex and the other polygon's plane. Check to make sure that the line (spanning from the vertex to the nearest point on the plane) is inside the other polygon; if it's not, then the shortest line to the other polygon will be on its perimeter, which was already taken care of in case 1 or 2.
(make sure to do this check for both polygons)

For case 5, at least one line segment must intersect with the area of the other polygon - if they intersected on their perimeters, we would have caught it already in cases 1-3, and if a vertex intersected the area, we would have caught it in case 4. So simply check the intersection of each edge with the other polygon's plane and see if the intersection point is inside the other polygon.
(make sure to do this check for both polygons)

Take the minimum distance found in all of that, and we're done.

Answer 2

This is a simple bounded optimization with linear constraints and a quadratic goal function. There are many algorithms which can be used, such as gradient descent.

Answer 3

What most people have proposed on this thread is "take all points/edges of one polygon and compare to each points/edges of the other". This is probably going to work fine if all you do is compare two fairly simple polygons and if you are not too concerned with doing this quickly.

However, if you want a fairly easy and better method. Use, as suggested by Ben Voigt, a quadratic optimization method (i.e. Quadratic Programming). Basically, your polygons are your set of linear constraints, i.e. your solution point must lie towards the inner-side of every edge of your polygon (that's an inequality constraint). And your cost-function to optimize is just the Euclidean distance, i.e. the Q in the standard formulation is just the identity matrix. Once cast as such a problem, you can either use a library that solves this (there are many of those out there), or you can study it from a book and roll your own code for it (it's a fairly easy algorithm to code up).

If you want a real method for doing this, for example, if that simple polygon-to-polygon test is the first step towards more complex 3D shapes (like a solid made of polygons). Then, you should most probably just use a package that already does that. Here is a set of collision detection libraries, many of which output penetration depth or, equivalently, minimum distance.

Answer 4

Its not clear what you've tried.

This looks likely for segments per se.

So then all you have to do is check all edge pairs. I'd look to implement that first before trying to optimise.

There is probably an optimisation in considering the vector from one centroid to the other and only considering edges that are in some sense in that direction.