Page 1 of 1

How To Compute Shortest Distance Between Two Lines

Posted: Fri Oct 13, 2006 4:23 am
by Alexis Blaze
problems:
given A=(x1,y1),B=(x2,y2),C=(x3,y3),D=(x4,y4)....
how to compute shortest distance between line AB to line CD...
if the lines intersect than distance = 0, if the lines not intersect, there would be a lot of possibillities, and that mean a lot of if else if else if...

is there some mathematical way to compute this? or any other simple way?

thanks in advances...

Posted: Fri Oct 13, 2006 3:56 pm
by misof
You probably want the distance of line segments, not the distance of the entire (infinite) lines, right?

There is no simple way to do this. The cases to consider are:
- if they intersect, answer = 0
- if not:
* compute the distance for each pair of endpoints
* for each endpoint, find its orthogonal projection onto the other line (infinite line containing the other segment), check whether the projection lies inside the other segment, and if yes, compute the distance
* return the minimum of all the distances computed above

Posted: Sun Oct 15, 2006 3:11 pm
by Planeyang
but if unfortunately. We meet two parallel lines.
No one projection lies inside the other segment.

What can we do

Posted: Sun Oct 15, 2006 8:00 pm
by Darko
Again, if you are talking about line segments on parallel lines:
* compute the distance for each pair of endpoints
In the case of parallel lines: pick a point on one line, get normal through that point and see where it intersects the other line.

Posted: Mon Oct 16, 2006 7:54 am
by DJWS
http://softsurfer.com/
This website contains a lot of algorithms about computational geometry.
You can search in this site and see what you want.

Here is a related problem in uva: 10514 River Crossing.
Give a try. :D
--
DJWS, a newbie in programming :wink:

Posted: Mon Oct 16, 2006 6:10 pm
by Alexis Blaze
thanks a lot... especially for the web site link... it really great!... :D