## How To Compute Shortest Distance Between Two Lines

Moderator: Board moderators

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

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?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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
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
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:
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.
--
DJWS, a newbie in programming

Alexis Blaze
New poster
Posts: 8
Joined: Thu Jul 13, 2006 8:36 am
Location: Indonesia
Contact:
thanks a lot... especially for the web site link... it really great!...