Two Polygons in 3D Space

Date: 01/31/2003 at 06:13:52
From: Brendon
Subject: The distance between 2 polygons in 3D space.

How do you find the shortest distance between two polygons in 3D 
space? This is for a 3D kind of application, but I have been puzzling 
over it for a little while and am not sure how to go about it or 
start it.

If you have 2 polygons represented in 3D space by n vertices, how do 
you find the shortest distance between them? Assume that each vertex 
is represented by the three variables x,y,z and we do not know how 
many vertices make up a polygon.

Date: 01/31/2003 at 09:58:55
From: Doctor Tom
Subject: Re: The distance between 2 polygons in 3D space.

Hi Brendon,

I think it is a very, very difficult problem with no nice solution.

And I am not just saying this after glancing at the problem and
thinking about it for two minutes - I worked in 3D computer graphics 
library design for about 20 years and worked on problems like this a 
lot.

Even for two triangles it is difficult. In fact, it is quite difficult 
to know if two triangles intersect in space, meaning the distance is
zero.

Assuming that the polygons could be concave (in other words, with 
indentations), it is a total nightmare - they could thread through 
each other any number of times without touching.

If I HAD to solve it, here's what I'd do:

Break each polygon down into triangles. This can be done without 
introducing any additional vertices, so an n-sided polygon will be 
broken down into n-2 triangles.

Find the distance between each pair of triangles. If your original 
polygons have m and n sides, this will just be a collection of 
(n-2)(m-2) numbers. Choose the smallest.

Now you just need to know how to compare two triangles:

1) Find if they intersect. If so, the distance is zero, and in fact 
   then you can quit the entire process, since you know that they'll 
   never get closer than zero.

2) If not, for each vertex of each triangle, project it onto the plane 
   of the other triangle and see if the projection lies inside it.  
   If so, the distance is that projection.

3) For each point, project it onto each edge of the other triangle.  
   If the projection lies inside the segment, the distance from the 
   point to the projection is the minimum.

4) For each vertex, find the distance to the three vertices of the 
   other triangle - 6 more lengths.

5) Compare all the numbers from 2, 3, and 4, and choose the minimum.   
   That's the answer for that pair of triangles.

Note that I have not even thought about when there are multiple 
closest pairs - to do so you'd have to look among all pairs of things 
(faces, exterior edges, faces with edges, etc.) and see which are 
parallel, and share parallel projections. I think this would be 
extremely ugly, uglier than what I described above.

If you really have to make this work in a graphics program, it'll be a 
LOT of work!

Good luck.


- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/31/2003 at 16:21:01
From: Brendon
Subject: Thank you (The distance between 2 polygons in 3D space.)

Thanks for the help. At least now I now know how much it would involve 
and that is a huge task. It could be done but I think before I even 
attempt to do that I might look for other methods. Thanks again for 
clarifying it. Sounds like it would take to much time to compute 
anyway even if  I could implement it.

Brendon.