Sign in to follow this  

Shortest distance between two parallel lines in 3D space

This topic is 2490 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey folks !

I can't seem find any information about this problem online. Should I project the two lines into the perpendicular plane and calculate the distance between those points, or is there an even better way of doing this?

Thanks in advance !

- Dave

Share this post


Link to post
Share on other sites
I wish I had a little more information on this but never actually had to do it myself. However back in the days of studying Ogre they had these things they called scene rays that where used to calculate positions along a straight line. I have also seen the term "Ray" used among other engines and technologies. Maybe searching for some more information on "Howto use Scene Rays <insert your engine / technology here>".

Share this post


Link to post
Share on other sites
How the two lines are represented? If they are represented in parametric form (so you have two points P and Q and a single direction dir), the distance you are looking for is the length of the component of (P - Q) perpendicular to dir. You can therefore use the formula:

d = length((P - Q) - dot(P - Q, dir)dir)

I have assumed dir to be of unit length.

Share this post


Link to post
Share on other sites
Also, for parallel lines you should just be able to project the origin of one line onto the other line (a trivial operation) and measure the distance between the two points.

Share this post


Link to post
Share on other sites
In practice I'm testing whether two specific polygon edges are close enough that you can walk between them. I'll paste the whole idea in case anyone wants to suggest some improvements:

Step 1: Find the angular difference through the dot product, if greater than an acceptable degree of error then break.
Step 2: Establish planes from the end points of each segment and use plane dot product to see if either of the other segment's end points is between those planes. If not, then the segments would be too far apart, even if they were on the same infinite line.
Step 3: Calculate the distance between the segments (as if they were infinite lines). Again, if this exceeds an acceptable degree of error then break, otherwise success !

I'm guessing step 2 and 3 could be swapped depending on which calculation is more costly (might wanna break before too much time has passed).

I have never heard of an origin of an infinite line, how would I find this?

Share this post


Link to post
Share on other sites
[quote]I have never heard of an origin of an infinite line, how would I find this?[/quote]
It's arbitrary - it's just an artifact of the representation.

A common representation for a line is:

O + tD

Where O (the origin) is any point known to lie on the line, and D (the direction) is a vector parallel to the line. The parameter [i]t[/i] can be any real-numbered value (mathematically speaking).

With the problem you described, a logical choice for the origin would be a vertex of the polygon edge, and for the direction, the vector from that vertex to the other edge vertex.

Share this post


Link to post
Share on other sites
[quote]In practice I'm testing whether two specific polygon edges are close enough that you can walk between them. I'll paste the whole idea in case anyone wants to suggest some improvements:[/quote]

The general problem is to find the closest distance between two infinite lines. The lines are not required to be parallel. Deriving a modified solution for finite line segments is a rather complicated process, but it's described very well on this website:

[url="http://www.softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm"]http://www.softsurfe...orithm_0106.htm[/url]

If you don't understand the math, you can just copy and paste their c++ implementation. You're looking for "dist3D_Segment_to_Segment"

Share this post


Link to post
Share on other sites

This topic is 2490 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this