Associated Topics || Dr. Math Home || Search Dr. Math

### 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.
```
Associated Topics:
College Higher-Dimensional Geometry
High School Higher-Dimensional Geometry

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search