How to find shortest distance between 2 polygons
 

How to find the shortest distance between 2 polygons in 3D space. I tried to figure out ways for finding the shortest distance between 2 polygons in 3D space but it is not all that straight forward. Would greatly appreciate any inputs on this.

Regards gama

Re: How to find shortest distance between 2 polygo
 

You are talking about 3D space, so do you really mean "polygon" or "polyhedral"? For polygons, it comes down to finding the distance between two lines.

Re: How to find shortest distance between 2 polygo
 

If those objects are limited (defined) by planes intersection, you need "linear programation" solvers.

Search for those kind of algorithms.

Re: How to find shortest distance between 2 polygo
 

thanks...a late reply from me. It has to be either from vertex to polygon surface or from edge to edge of polygon. Now the next question is, how to find the shortest distance between 2 edges (nor rays but finite line segments) in 3D.

Re: How to find shortest distance between 2 polygo
 

Do you know how to find the distance between two lines (of infinite length)? It's a minimization problem, kind of hard to describe in words. Each line is defined by a point (choose one of the vertices of the polygon) and a directional vector. If your two lines intersect or are even identical, the solution is trivial. If not, the shortest distance between the lines can be visualized as a segment on a third line which intersects each of your two lines perpendicularly. As you find the length of this segment between the intersections, you will also find the location of these intersections, and you can then determine if they fall within your polygon segments. If they do, you're done. If not, the problem reduces to finding the distance between the polygon vertices.

Re: How to find shortest distance between 2 polygo
 

The steps are

1. find the perpendicular distance between line to line and check whether the points lie inside the segments 2. If step one is not true then find the shortest distance between each of the vertices onto line and check whether the projected point lie inside the segment 3. if first two steps are not correct then it should be the distance between vertices

i guess these are lot of evaluation in case of large models.... so is there any other way

Re: How to find shortest distance between 2 polygo
 

No, that's pretty much it. You could try to find smarter ways to test the situation (1 versus 2 or 3), but it wouldn't make a huge difference in computational effort.

The question you need to ask youself is: How accurately do you really need this? Does this really have to be an exact solution, or is it OK to use a more heuristic approach which could greatly reduce the effort. I guess it depends on your application. If this is part of a numerical method which does not yield an exact solution anyway, it would not be wise to spend a lot of effort to get an exact solution in just one aspect of the algorithm. For example, if you were to use a finite-volume method which assumes an average flux value for the whole face of a cell, it would make no sense to treat the cell geometry in exact details.

Re: How to find shortest distance between 2 polygo
 

Just as a follow up to previous discussion...it is alrite to get nearest points on the polygon. For me the ultimate objective is to get nearest distance of 2 parts. The part could be of any irregular shape and is discretised with either hexahedral or shell elements. Currently what i am doing is to loop over all the nodes of one part and check their distance with all the nodes on the other part and vice versa. This leads to m*n searches if 2 parts have m and n nodes respectively, an expensive affair. I do not want to do this. Is there any numerical or some mapping technique which could lead me to a quick solution, i would definitely trade accuracy against time.

Re: How to find shortest distance between 2 polygo
 

I am assuming, m and n are large numbers. Then, there are ways to speed this up. Try to work with bounding boxes. Let's say you have a part that consists of n nodes in 3D space. You can create a set of 8 boxes (2x2x2) to enclose the whole part, essentially dividing the n nodes into 8 boxes. You do the same with part 2. Then you check which of the boxes of part 1 comes closest to the boxes of part 2 (or even intersect them). Now you are left with one box each (containing about 1/8th of the original number of nodes), for each part. You again subdivide each box by 8, and continue the above process until your number of nodes is reduced to a manageable value. This may seem like additional work, but if n and m are large it will considerably speed up your search.

This technique is very common in graphics applications. Check out "bounding volume" in Wikipedia.