I need a fast algorithm to determine if two line segments intersect.

Any help would be greatly appreciated.

Thanks!

I need a fast algorithm to determine if two line segments intersect.

Any help would be greatly appreciated.

Thanks!

From the FAQ:Quote:>I need a fast algorithm to determine if two line segments intersect.

>Any help would be greatly appreciated.

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?

2 post • Page:**1** of **1**