Page 1 of 1

### 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?

### Re: Finding whether 2 line segments intersect

Posted: Tue Aug 30, 2011 10:14 pm
I would say it is flawed. The only obvious thing that might work and occurred to me would be to change condition 1 in the following way:
1. The bounding box for the one segment intersects the other segment, and vice versa.

So not the bounding boxes, but a stronger condition. It sounds like it could work, but at this time of day I can't be bothered to prove it.
Besides, as this has to hold universally, you should be able to assume the bounding box would be identical to the line, making my altered statement trivial; however, I don't know the precise definition of bounding box used in the book.

### Re: Finding whether 2 line segments intersect

Posted: Wed Aug 31, 2011 2:47 am
Their definition of a bounding box is the smallest rectangle with sides parallel to the x and y axes that can hold the object. So for a line segment, the 2 endpoints would form opposite corners of the box.

Ah well, it may be possible to get away without using this algorithm. I wonder if the following works though. Take line segment p1p2 and determine which side of the line p3 and p4 are on. If they're on opposite sides, assuming 2 dimensions, I think that would mean line p1p2 must intersect segment p3p4. The segment can't be on both sides of the line without crossing it. If I could show line p1p2 must instersect line segment p3p4 and line p3p4 must intersect line segment p1p2, that must mean both line segments intersect.

Ah well, any good resources out there for learning computational geometry?

### Re: Finding whether 2 line segments intersect

Posted: Wed Aug 31, 2011 8:00 am
mdean wrote:I wonder if the following works though. Take line segment p1p2 and determine which side of the line p3 and p4 are on. If they're on opposite sides, assuming 2 dimensions, I think that would mean line p1p2 must intersect segment p3p4. The segment can't be on both sides of the line without crossing it. If I could show line p1p2 must instersect line segment p3p4 and line p3p4 must intersect line segment p1p2, that must mean both line segments intersect.
That works and is exactly what I use. You can still throw in a bounding box test first if that speeds things up.