# How to find shortest distance between 2 polygons

 Register Blogs Members List Search Today's Posts Mark Forums Read

 March 22, 2007, 14:00 How to find shortest distance between 2 polygons #1 gama 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 Mani 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 Guillermo Marraco 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 Ramesh 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 Mani 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 gama 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 Mani 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 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.

 April 5, 2007, 06:58 Re: How to find shortest distance between 2 polygo #8 Ramesh 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 Mani 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 Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are On Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post gruber OpenFOAM 9 February 15, 2012 07:22 tuks_123 CFX 10 April 15, 2011 11:20 ivan_cozza OpenFOAM Running, Solving & CFD 0 May 8, 2009 12:49 Student Main CFD Forum 2 August 4, 2005 22:33 Frank Main CFD Forum 1 July 5, 2005 10:07

All times are GMT -4. The time now is 17:19.