CFD Online Logo CFD Online URL
www.cfd-online.com
[Sponsors]
Home > Forums > Main CFD Forum

How to find shortest distance between 2 polygons

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

Reply
 
LinkBack Thread Tools Display Modes
Old   March 22, 2007, 14:00
Default 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

  Reply With Quote

Old   March 22, 2007, 16:22
Default 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.
  Reply With Quote

Old   March 28, 2007, 10:23
Default 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.
  Reply With Quote

Old   April 3, 2007, 06:42
Default 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.
  Reply With Quote

Old   April 3, 2007, 09:10
Default 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.
  Reply With Quote

Old   April 3, 2007, 13:57
Default 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
  Reply With Quote

Old   April 4, 2007, 08:58
Default 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.
  Reply With Quote

Old   April 5, 2007, 06:58
Default 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.
  Reply With Quote

Old   April 5, 2007, 08:18
Default 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.
  Reply With Quote

Reply

Thread Tools
Display Modes

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are On


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


All times are GMT -4. The time now is 07:08.