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

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.

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.

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?

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

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:

http://www.softsurfe...orithm_0106.htm

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