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.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.