The distance between two convex polygons in 3D

Question

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

What is the easiest way to calculate the closest distance between these two polygons?

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

Answer 1

This is a simple bounded optimization with linear constraints and a quadratic objective function. There are many algorithms that can be used, for example, gradient descent.

Answer 2

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

• Between two peaks
• Between the edge and the top
• Between two edges (imagine two polygons on perpendicular planes)
• Between the top and the inside of the polygon
• Or polygons intersect

Cases 1-3 are all taken care of, considering each pair of edges + vertices as a line segment and listing the distance between all pairs of line segments.

In case 4, find the distance between each vertex and another plane of the polygon . Make sure that the line (spanning from the top to the nearest point on the plane) is inside another polygon; if this is not so, then the shortest line to another polygon will be along its perimeter, which has already been taken care of in case 1 or 2.
(be sure to do this check for both polygons)

For case 5, at least one line segment must intersect with the region of another polygon - if they intersect at their perimeters, we would catch it already in cases 1-3, and if the vertex intersected the region, we would catch it in case 4. So just check the intersection of each edge with another plane of the polygon and see if the intersection point is inside another polygon.
(be sure to do this check for both polygons)

Take the minimum distance found in all of this and we are done.

Answer 3

What most people suggested in this thread is "take all the points / edges of one polygon and compare them with each point / edges of the other." This will probably work fine if everything you do compares two fairly simple polygons, and if you're not too concerned about it quickly.

However, if you want a fairly simple and better method. Use, as Ben Voigt suggested, a quadratic optimization method (i.e., quadratic programming ). Basically, your polygons are your set of linear constraints, i.e. The point of your decision should lie toward the inside of each edge of your polygon (which is a limitation of inequality). And your economic function for optimization is just the Euclidean distance, i.e. Q in the standard formulation is just the identity matrix. After you select this problem, you can either use a library that solves this problem (there are many), or you can study it from a book and load your own code for it (this is a fairly simple algorithm for encoding).

If you need a real method for this, for example, if this simple test with a polygon on a polygon is the first step to more complex three-dimensional shapes (for example, solid from polygons). Then you are most likely just using a package that already does this. Here is a collection of collision detection libraries, many of which infer the depth of penetration or, equivalently, the minimum distance.

Answer 4

It is unclear what you tried.

This most likely applies to segments as such.

So all you have to do is check all pairs of edges. I would try to implement this before trying to optimize.

There is probably an optimization when considering a vector from one centroid to another and only taking into account the edges, which in a sense are in this direction.

Answer 5

Scroll through all the vertices of the first object, then in this cycle draw all the vertices of the second object. In your inner loop, compare the distance between the two current vertices and keep the lowest distance. I do this all the time and as long as you don't have a ridiculously large grid, it's pretty instantaneous.