How To Compute Shortest Distance Between Two Lines

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Alexis Blaze
New poster
Posts: 8
Joined: Thu Jul 13, 2006 8:36 am
Location: Indonesia
Contact:

How To Compute Shortest Distance Between Two Lines

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

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post 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

Planeyang
New poster
Posts: 9
Joined: Sun Oct 15, 2006 1:31 pm
Location: China

Post by Planeyang »

but if unfortunately. We meet two parallel lines.
No one projection lies inside the other segment.

What can we do

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

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

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post 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:

Alexis Blaze
New poster
Posts: 8
Joined: Thu Jul 13, 2006 8:36 am
Location: Indonesia
Contact:

Post by Alexis Blaze »

thanks a lot... especially for the web site link... it really great!... :D

Post Reply

Return to “Algorithms”