Hi Dan,

you are talking about *line segments* and not *lines* because a line is infinite and
two lines do always
intersect in case they are not coincident or parallel.
But here is the solution:

Assuming:
we call the red line: line a with the start/end points P1 (x1,y1) and P2 (x2,y2)
and the purple line: line b with the start/end points P3 (x3,y3) and P4 (x4,y4)

the equations are:
Pa = P1 + ua ( P2 - P1 )
Pb = P3 + ub ( P4 - P3 )

with the two unknowns ua and ub,.
... but we can solve this for Pa=Pb because this is the point the lines do intersect:

ua = ((x4-x3)(y1-y3) - (y4-y3)(x1-x3)) / ((y4-y3)(x2-x1) - (x4-x3)(y2-y1))

ub = ((x2-x1)(y1-y3) - (y2-y1)(x1-x3)) / ((y4-y3)(x2-x1) - (x4-x3)(y2-y1))

Note that the two denominators are the same. If the denominator is 0 the
two lines are parallel (and so will not intersect) and if the numerator is also 0
the two lines are coincident.

But you are looking for the intersection and here it is:

x = x1 + ua (x2 - x1)
y = y1 + ua (y2 - y1)

sorry, not finished yet because this is the intersection for the two lines, but
you want to know if the line *segments* do intersect, but this is easy:
if both ua and ub lie in the range of 0 to 1 the two line segments DO intersect
in any other case they miss each other.

so long
-Ive

Post a reply to this message