Line Segment Intersection in 2 Dimensions Explained
08 Feb 2013
Geometric things have always been really tricky to program for me, and quite a lot of other people as well. I think I need more practice coding geometric stuff and explaining them in a post would help me remember them well. So I decided this would be the first step since finding whether two line segments on a cartesian plane intersect or not is pretty much the simplest problem to be faced in computational geometry. And hopefully, this will be the first in a series of blog posts.
So, how do we find whether two lines are intersecting? In the first example; consider the red line segment, and the line segment from top of red segment to both ends of the green segment.Call them , and respectively.
Notice that both of the vectors are to the right of the line segment.
One of the vectors is to the left of the red line, and the other is to the right of it
So, just check whether the opposite ends of the second segment are on the opposite sides of the first segment, right? Well, there is an (pretty obvious) exception to that:
In this case; one end of the green line segment is to the left of the red one and the other one is to the right, but they don’t intersect. To solve this, just check for both line segments.
See how both ends of the green segment is to the left of the red one in this flipped graph?
Leftward or rightward?
That leaves us with one more question, how do we find out if a vector is to the left or to the right of another one. And the answer for that, is the Cross Product. The cross product results in a vector perpendicular to the plane the vectors and are in, so in case of 2-dimensional vectors, the resultant vector only has the z component. For 2-Dimensional vectors; the cross product is calculated as
Due to the anticommutativity1 of the cross product, we can find the order vectors are oriented, i.e. whether a vector is to the left or right of the other one2. In 2-dimensions; If ; is to the right of , and vice versa if the product is negative. The vectors are collinear if the cross product is equal to zero. There is a right-hand rule for that, but most of the times, I can’t remember the rule, the easy way to come up with is just check the cross product of two vectors, say and see if it is positive or negative.
One Last Corner Case
If two line segments lie on the same line, this method will always return false, whether there is overlap between line segments or not. To cover this case, we can check for both ends of the second line if they are within the first line or not. To do that; we can find the corresponding line to the line segment (, ) – (, ), which is
and test if the point tested satisfies the equation and check if its x coordinate lies between and . If one of the endpoints of the second line segment is contained within the first one, then those line segments intersect.
The code(for line segment intersection, the demo and drawing line segments on canvas) can be found here: https://github.com/kuzux/kuzux.github.com/blob/master/line-segment-intersection.js
And the Demo
Usage: Just click around in the area below :)
Actually, what we’ve found is if the turn from to is clockwise or counterclockwise, and leftward and rightward are only valid in first two quadrants of the 2 dimensional cartesian coordinate system, and since in this case, we’re only checking whether the vectors are on the same side or not, this distinction doesn’t really matter. ↩