Need line/line intersection algorithm

Need line/line intersection algorithm

Post by J. Brent Spear » Fri, 12 Jan 1996 04:00:00



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

Thanks!

 
 
 

Need line/line intersection algorithm

Post by Joseph O'Rour » Sun, 14 Jan 1996 04:00:00




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

From the FAQ:
ftp://rtfm.mit.edu/pub/usenet-by-group/news.answers/graphics/algorith...

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,"

 
 
 

1. sweep line algorithm for line 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)
thanks in advance

2. OpenGL

3. need a line/circle intersection algorithm

4. FS Indy Presenter Flat Panel Display

5. Needing algorithm for intersection between line and ellipse

6. Rotation around a vector...

7. Needing algorithm for intersection between line and any object

8. Need line/rectangle intersection algorithm

9. line/surface intersection algorithm needed

10. Shortest Line Seg tween 2 3D Line Segment Algorithm Needed

11. Intersection of line segment with bounding box or other line segment

12. How to: (3d) line with line intersection?