8

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.

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
Dmi
  • 645
  • 1
  • 11
  • 22
  • Are you looking for the distance between their centroids, or the distance between their two closest edges? – Joshua Rodgers Feb 25 '11 at 00:00
  • 3
    So not the distance between the two closest points then? How are you defining "closest edge" and, given a suitable definition, how are you defining the distance between the two closest edges? – Troubadour Feb 25 '11 at 00:20
  • 1
    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. – Dmi Feb 25 '11 at 00:41
  • 1
    That is not the two closest edges, that is the two closest points. In which case, +1, great question :) – BlueRaja - Danny Pflughoeft Feb 25 '11 at 01:28
  • Note that if the two polygons are parallel then the shortest line is not unique ;) But since all these shortest lines have the same length, the distance is still well defined. – Alink Feb 25 '11 at 06:17

5 Answers5

3

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.

Community
  • 1
  • 1
BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • This seems straightforward enough, I'll try this out. – Dmi Feb 25 '11 at 03:30
  • I think you forget to mention the case where the 2 polygons are parallel. It's included in 1-4, so no problem, but better keep that in mind when doing the maths for projections etc. Because searching intersection point without considering the parallel case often cause nasty errors. For example, the check for 5 need to watch this (intersection of each edge with the other polygon's plane). – Alink Feb 25 '11 at 06:27
  • @Alink: Correct, I did not mention this because it's included in 1-4, but it is something to worry about. The edge/inside-of-other-polygon case is another one: it's included in cases 3-4, but still something to be aware of (at the very least for testing). – BlueRaja - Danny Pflughoeft Feb 25 '11 at 13:10
  • @Dmi: I see you marked this correct. I really think you should consider @Ben Voigt's solution; it is the true correct answer. – BlueRaja - Danny Pflughoeft Feb 25 '11 at 16:20
  • 1
    Thanks, I've actually implemented this now and it works well. I'll also take a look at the other method after reading about Quadratic programming a bit more. – Dmi Feb 25 '11 at 21:53
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.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • Could you please explain a bit further - what would the quadratic goal function be? – BlueRaja - Danny Pflughoeft Feb 25 '11 at 02:28
  • The goal is "minimize (x2 - x1)**2 + (y2 - y1)**2 + (z1 - z1)**2". The points which give the minimum distance also give the minimum distance squared. – Ben Voigt Feb 25 '11 at 02:38
  • Ah, and the constraints would be "x1, y1, z1 lie on such-and-such plane," and "x1, y1, z1 lie on this half of the plane" for each edge. Brilliant! As long as you can divide a plane in half in 3D-space using a single equation *(which I believe you can, but to be honest I haven't put any thought into it)*, this will work, and will easier and less error-prone than my method. +1! – BlueRaja - Danny Pflughoeft Feb 25 '11 at 13:22
  • @BlueRaja: A linear inequality creates a half-space. A linear equality creates a plane (which can be expressed as the intersection of two inequalities), and then intersecting more half-spaces ultimately allows any convex shape. – Ben Voigt Feb 25 '11 at 15:09
2

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.

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
Mikael Persson
  • 18,174
  • 6
  • 36
  • 52
  • Thanks, that looks like an interesting topic. I'm not going towards more complex shapes, just looking for simple distance-pairs for 3D faces. – Dmi Feb 25 '11 at 03:28
1

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.

Keith
  • 6,756
  • 19
  • 23
  • @BlueRaja, @Dmi. OK, missed the noted case. It still looks to me like a relatively dumb algorithm ought to work. Is the issue with computing the distances between primitive (surface, edge, vertex) pairs , or determining which sets of primitive pairs need to be computed? Or being sure that even checking all primitive pairs meet the requirement? – Keith Feb 25 '11 at 01:57
  • This would be good, except that it's possible for one polygon to "touch" the other polygon in its center at a right angle. In this case, the second polygon will have an edge or vertex that touches the plane of the first polygon while still being at a distance from the edges of the first polygon. – Dmi Feb 25 '11 at 02:10
-3

Loop through all the vertices of the first object, then in that loop, loop through all the vertices of the second object. In your innermost loop, compare the distance between the two current vertices and store the lowest distance. I do it this way all the time and as long as you don't have a ridiculously large mesh, it pretty much instantaneous.

Davido
  • 2,913
  • 24
  • 38
  • 3
    The vertices might not line up. For example, it's possible for these two polygons to touch each other at a right angle, with one of the second polygon's vertices touching the first polygon in the center. – Dmi Feb 25 '11 at 00:10