Re: Distance between segments

zaknospam@xxxxxxxxx wrote:
Hi NG!

I have a little problem, and I hope that someone may help me...

I have two finite 2D line segments, and I have to find:

1) the parts of the two segments that are near a certain distance.

What on earth does "near a certain distance" mean?

2) the two points on each segment that are nearest

I mean:
- if the segment A is defined by its two ending points Pa0=(Xa0, Ya0),
Pa1=(Xa1, Ya1)
- if the segment B is defined by its two ending points Pb0=(Xb0, Yb0),
Pb1=(Xb1, Yb1)

I have to find:
- the starting and ending position on A (measured as distances from
Pa0) of the part of the segment which points are far less than a fixed
distance D from B

What does "far less than a fixed distance D" mean? If you want an exact
answer then you need to give an exact problem statement. Something like
"less than a fixed distance D" for example.

- the same as above for the segment B
- the position on A and on B where they are nearest

I've tried to do all that on my own, but after some time (well, In fact
a lot of time) I'm giving up...
Does anyone can help this depressed guy?

Thank you a lot!

As indicated, I don't understand question 1. As far as question 2 is
concerned...

I'll denote the line segments (x1,y1) - (x2,y2) and (x3,y3) - (x4,y4).
There are several cases to consider.

If the lines intersect at a point lying on both line segments, then the
minimum distance between the segments is zero. Let

t = ((x3 - x1)*(y4 - y3) - (y3 - y1)*(x4 - x3)) / ((x2 - x1)*(y4 -
y3) - (y2 - y1)*(x4 - x3))
u = ((x3 - x1)*(y2 - y1) - (y3 - y1)*(x2 - x1)) / ((x2 - x1)*(y4 -
y3) - (y2 - y1)*(x4 - x3))

Then the point of intersection lies on both segments if and only if 0
<= t <= 1 and 0 <= u <= 1. The point of intersection is at (x,y), where

x = x1 + t*(x2 - x1) = x3 + u*(x4 - x3)
y = y1 + t*(y2 - y1) = y3 + u*(y4 - y3)

If the denominator in the expressions for t and u is zero then the
lines are parallel (see later).

If the point of intersection lies outside one or both line segments,
then the shortest distance between the two segments is either a line
between two endpoints or a perpendicular line from an endpoint on one
segment to the other segment, where the foot of the perpendicular lies
on the latter segment.

I can't immediately think of a general way to find the shortest of
these that's any easier than calculating them all and comparing (apart
from the unmathematical method of drawing the lines and seeing if it's
"obvious"). The distances between endpoints are easy. For example, the
distance between (x1,y1) and (x3,y3) is sqrt((x3 - x1)^2 + (y3 -
y1)^2), and similarly for the other pairs of endpoints.

To deal with the second case, let (p,q) be the endpoint from which the
perpendicular is dropped, and let the target line segment be (x1,y1) -
(x2,y2). Let

t = ((p - x1)*(x2 - x1) + (q - y1)*(y2 - y1)) / ((x2 - x1)^2 + (y2 -
y1)^2)

The foot of the perpendicular lies on the target line segment if and
only if 0 <= t <= 1. If it doesn't then this is not a candidate
solution. The foot of the perpendicular lies at (x,y) where

x = x1 + t * (x2 - x1)
y = y1 + t * (y2 - y1)

If the line segments are parallel then there is either a unique
endpoint-to-endpoint shortest distance, or an infinite number of lines
of shortest distance. In the latter case the above method will find
two, three, or four of them (perpendicular lines from the endpoints of
one segment to the other segment).

.

Relevant Pages

  • Re: Looking for algo. to find points along alignment
    ... the vectors between the point and the endpoints onto the line ... recurse until you find a single segment or the group of segments no ... Given a bounding rectangle and the station point, ... it is somewhere between the distance to furthest ...
    (comp.programming)
  • Re: OT:Three questions for Scott
    ... and then left her for a younger woman (Cindy). ... watching that segment it is hard to see "Country First". ... It had to do with Congress laying restrictions ... on long distance flights to and from NAtional ...
    (rec.audio.opinion)
  • Re: OT:Three questions for Scott
    ... and then left her for a younger woman (Cindy). ... watching that segment it is hard to see "Country First". ... It had to do with Congress laying restrictions ... on long distance flights to and from NAtional ...
    (rec.audio.opinion)
  • Re: Distance between two points
    ... Can someone tell me the formula to calculate the curved distance between ... Draw a line segment between P1 and P2. ... P1-P2 line segment is an attempt at drawing the curve centered at ... Note that C1MP1 is a right triangle with the right angle ...
    (sci.crypt)
  • Re: Minimum Distance of Random Points on a Line
    ... before the distance calculation begins, ... one point from each set is contained in that segment. ... distance between those endpoints. ... The minimum distance between any two points on the line, ...
    (sci.math)