
[Sponsors] 
March 22, 2007, 14:00 
How to find shortest distance between 2 polygons

#1 
Guest
Posts: n/a

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 

March 22, 2007, 16:22 
Re: How to find shortest distance between 2 polygo

#2 
Guest
Posts: n/a

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.


March 28, 2007, 10:23 
Re: How to find shortest distance between 2 polygo

#3 
Guest
Posts: n/a

If those objects are limited (defined) by planes intersection, you need "linear programation" solvers.
Search for those kind of algorithms. 

April 3, 2007, 06:42 
Re: How to find shortest distance between 2 polygo

#4 
Guest
Posts: n/a

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.


April 3, 2007, 09:10 
Re: How to find shortest distance between 2 polygo

#5 
Guest
Posts: n/a

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.


April 3, 2007, 13:57 
Re: How to find shortest distance between 2 polygo

#6 
Guest
Posts: n/a

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 

April 4, 2007, 08:58 
Re: How to find shortest distance between 2 polygo

#7 
Guest
Posts: n/a

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 finitevolume 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. 

April 5, 2007, 06:58 
Re: How to find shortest distance between 2 polygo

#8 
Guest
Posts: n/a

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.


April 5, 2007, 08:18 
Re: How to find shortest distance between 2 polygo

#9 
Guest
Posts: n/a

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. 

Thread Tools  
Display Modes  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Find a particle's distance to a wall  gruber  OpenFOAM  9  February 15, 2012 07:22 
Ways to find Mass transfer coefficient using CFD?  tuks_123  CFX  10  April 15, 2011 11:20 
How to find cells within a distance  ivan_cozza  OpenFOAM Running, Solving & CFD  0  May 8, 2009 12:49 
Wall distance  Student  Main CFD Forum  2  August 4, 2005 22:33 
where to find code for nearest wall distance  Frank  Main CFD Forum  1  July 5, 2005 10:07 