### Finding whether 2 line segments intersect

Posted:

**Tue Aug 30, 2011 9:27 pm**I recently cracked open my old Algorithms book and found a method of determining if 2 line segments intersect. If I'm understanding this text correctly, though, the method is flawed. The method has 2 steps for determining if the segment from p1 and p2 intersects the segment from p3 and p4.

1. Determine if the 2 bounding boxes for each segment intersect.

2. Determine if the directed segments p1p3 and p1p4 have opposite orientations relative to p1p2.

The text says the 2 segments intersect if and only if both conditions are true. Unless I'm missing something, the following is a counterexample:

p1=(0,0),p2=(3,3),p3=(0,2),p4=(9,8)

The bounding boxes intersect at 0<x<3 and 2<y<3, so condition 1 holds. p1p4 is clockwise relative to p1p2 while p1p3 is counterclockwise relative to p1p2, so condition 2 holds. But the 2 line segments don't intersect. The line p1p2 would intersect the segment p3p4 at (6,6).

So am I missing something or did my textbook screw up?

1. Determine if the 2 bounding boxes for each segment intersect.

2. Determine if the directed segments p1p3 and p1p4 have opposite orientations relative to p1p2.

The text says the 2 segments intersect if and only if both conditions are true. Unless I'm missing something, the following is a counterexample:

p1=(0,0),p2=(3,3),p3=(0,2),p4=(9,8)

The bounding boxes intersect at 0<x<3 and 2<y<3, so condition 1 holds. p1p4 is clockwise relative to p1p2 while p1p3 is counterclockwise relative to p1p2, so condition 2 holds. But the 2 line segments don't intersect. The line p1p2 would intersect the segment p3p4 at (6,6).

So am I missing something or did my textbook screw up?