## Need line/line intersection algorithm

### Need line/line intersection algorithm

I need a fast algorithm to determine if two line segments intersect.
Any help would be greatly appreciated.

Thanks!

### Need line/line intersection algorithm

Quote:>I need a fast algorithm to determine if two line segments intersect.
>Any help would be greatly appreciated.

From the FAQ:

Subject: 8) How do I find intersections of 2 2D line segments?

This problem can be extremely easy or extremely difficult depends
on your applications.  If all you want is the intersection point,
the following should work:

Let A,B,C,D be 2-space position vectors.  Then the directed line
segments AB & CD are given by:

AB=A+r(B-A), r in [0,1]
CD=C+s(D-C), s in [0,1]

If AB & CD intersect, then

A+r(B-A)=C+s(D-C), or

XA+r(XB-XA)=XC+s(XD-XC)
YA+r(YB-YA)=YC+s(YD-YC)  for some r,s in [0,1]

Solving the above for r and s yields

(YA-YC)(XD-XC)-(XA-XC)(YD-YC)
r = -----------------------------  (eqn 1)
(XB-XA)(YD-YC)-(YB-YA)(XD-XC)

(YA-YC)(XB-XA)-(XA-XC)(YB-YA)
s = -----------------------------  (eqn 2)
(XB-XA)(YD-YC)-(YB-YA)(XD-XC)

Let I be the position vector of the intersection point, then

I=A+r(B-A) or

XI=XA+r(XB-XA)
YI=YA+r(YB-YA)

By examining the values of r & s, you can also determine some
other limiting conditions:

If 0<=r<=1 & 0<=s<=1, intersection exists
r<0 or r>1 or s<0 or s>1 line segments do not intersect

If the denominator in eqn 1 is zero, AB & CD are parallel
If the numerator in eqn 1 is also zero, AB & CD are coincident

If the intersection point of the 2 lines are needed (lines in this
context mean infinite lines) regardless whether the two line
segments intersect, then

If r>1, I is located on extension of AB
If r<0, I is located on extension of BA
If s>1, I is located on extension of CD
If s<0, I is located on extension of DC

Also note that the denominators of eqn 1 & 2 are identical.

References:

[O'Rourke] pp. 249-51
[Gems III] pp. 199-202 "Faster Line Segment Intersection,"

this question goes for anyone who is familiar with and has tried to
implement the sweep line algorithm to find all intersections between a
group of sections. my problem is: supose my sweep line moves from left
to right. how do i sort vertical sections in the status data structure.
(the definition of the Status sorting function does not cover the cse of
vertical lines)