Finding whether 2 line segments intersect

Shape and space, angle and circle properties, ...
Post Reply
mdean
Posts: 141
Joined: Tue Aug 02, 2011 1:05 am

Finding whether 2 line segments intersect

Post by mdean » Tue Aug 30, 2011 8: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?
Image

User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 9:43 am
Location: Netherlands

Re: Finding whether 2 line segments intersect

Post by Lord_Farin » Tue Aug 30, 2011 9: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.
Image

mdean
Posts: 141
Joined: Tue Aug 02, 2011 1:05 am

Re: Finding whether 2 line segments intersect

Post by mdean » Wed Aug 31, 2011 1: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?
Image

User avatar
jaap
Posts: 515
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Finding whether 2 line segments intersect

Post by jaap » Wed Aug 31, 2011 7: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.

Post Reply