Navigating Line Segments
If you’re given a problem to find out whether two line-segments intersect, there is an easy approach to this. It involves finding the orientation of the line segments. If they’re different, they intersect.
Each line segment has a start-point and an end-point. Our first line will be represented by (a1,b1) and our second line will be represented by (a2,b2).
To test if they intersect, we need to verify the following condition:
What does this mean exactly? Let’s jump into an example and find out.
It’s clear to us that the two line-segments intersect, but it’s not clear to your computer. We need to test it with the condition outlined above. Let’s walk through each step.
First, we’ll look at the orientation of (a1,b1,a2). We can see that this orientation is clockwise.
Next, we move to (a1,b1,b2). The orientation is counterclockwise, therefore, (a1,b1,a2) and (a1,b1,b2) are oriented differently.
We’ll have to test the second part to make sure that the orientation between those pairs is also different. The orientation for (a2,b2,a1) is counterclockwise.
Next, we move to (a2,b2,b1). The orientation is clockwise, therefore, (a2,b2,a1) and (a2,b2,b1) are oriented differently.
Since both (a1,b1,a2) and (a1,b1,b2) are oriented differently, and (a2,b2,a1) and (a2,b2,b1) are oriented differently, we know that the lines intersect.
If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.