Line Segment Intersection Algorithm
November 11th I’ll be participating in the Southern California Regional ACM programing competition. This is my second time competing as well as Adam’s. One of our practice problems involved finding if a wall blocks the path between two points. At the time the only way I could think of doing this involved solving for the intersection, and then checking to make sure the intersection point is contained within the domain and range of both segments.
Upon looking at the solution I noticed whoever wrote it had a method called signedarea which I was determined to figure out as the solution was much more elegant than mine. After searching this morning I came across a simpler way (and this) to determine if two line segments intersect.
The solution involves determining if three points are listed in a counterclockwise order. So say you have three points A, B and C. If the slope of the line AB is less than the slope of the line AC then the three points are listed in a counterclockwise order.
This is equivalent to:
def ccw(A,B,C): return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)
You might be wondering how does this help? Think of two line segments AB, and CD. These intersect if and only if points A and B are separated by segment CD and points C and D are separated by segment AB. If points A and B are separated by segment CD then ACD and BCD should have opposite orientation meaning either ACD or BCD is counterclockwise but not both. Therefore calculating if two line segments AB and CD intersect is as follows:
def intersect(A,B,C,D): return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
I’ve created a python script which demonstrates this algorithm.
Related Entries
Comments
Comment from Hammoudeh
Time December 8, 2008 at 8:38 am
cool. I was using the code provided from: http://mail.python.org/pipermail/python-list/2000-November/059143.html
but your solution is much shorter and easier to understand.
Good job
Comment from Bryce Boe
Time December 8, 2008 at 12:09 pm
Hammoudeh,
Thanks for the comment. The email on the python list is a ridiculous amount of code to solve the problem. I’m glad you were able to find a more elegant solution.
Comment from Haibao Tang
Time December 23, 2008 at 9:35 am
This method does not handle the case where an end-point of one segment is inside another segment, in which case the ‘counter-clock-wiseness’ is undefined … for example, add this line in your script “print intersect(a,d,c,d)” will return False, which obviously is incorrect.
Comment from Bryce Boe
Time December 23, 2008 at 11:37 am
Good call Haibao, you are correct. This algorithm assumes the endpoints are not closed thus a test for collinearity is required to be complete.
Comment from lolhmm
Time April 1, 2009 at 11:48 am
Could the issue Tang pointed out be solved by altering the CCW test to;
((cy-ay*bx-ax)) >= ((by-ay)*(cx-ax))
Sorry I didn’t test before commenting, just came across this and thought it might do the trick. :p
Delete this comment if it’s incorrect please, otherwise success!
Comment from Bryce Boe
Time April 1, 2009 at 12:07 pm
Random commenter:
“If the slope of the line AB is less than the slope of the line AC then the three points are listed in a counterclockwise order.”
If the slopes are equal then all three points are collinear and therefore no longer listed in a counterclockwise order which breaks this intersection algorithm.
Pingback from Intel Threading Challenge – Problem 6: Line Segment Intersection – SLUUM
Time August 12, 2009 at 8:47 am
[...] we have a simple implementation of line segment intersection in the plane: source (based on http://www.bryceboe.com/2006/10/23/line-segment-intersection-algorithm/). Attached Files:line_interVN:F [1.6.1_878]please wait…Rating: 0.0/10 (0 votes cast) This entry [...]
Comment from doc
Time September 7, 2009 at 6:30 am
@lolhmm et al
No it won’t since you have to had different ccw results in tests ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D), while for collinear case your code just treats collinearity as ccw.
I have rewritten ccw function to something like this (code in C/C++):
—
double ccw = (C(1) – A(1)) * (B(0) – A(0)) – (B(1) – A(1)) * (C(0) – A(0));
return ccw > 0.0 ? 1 : ccw < 0.0 ? -1 : 0;
—
A(0) is A.x, A(1) A.y and so on
Not havily tested yet but seems to work…
Comment from Cheri
Time October 26, 2006 at 5:25 pm
What the heck are you even talking about?
Tom said this was cool. I’ll have to take his word for it since I’m merely a non-practicing lawyer. Good job on the copyright notice at the bottom of your weblog. I’ve taught you well, Grasshopper. Okay, it probably wasn’t me who told you to do that, but still, good job.