Problem: Determine if two line segments, defined by their end points, intersect.
bool intersection(struct point * start1, struct point * start2, struct point * end1, struct point * end2){
...
}
Solution: Let's start with an example to make sure that we understand this problem. Pic 1 shows an example where two lines intersect and pic 2 shows when they do not.
We need to return true in the case of pic1 and false in the case of pic 2.
Let's see if the pictures help to guide us to the solution. In pic 1, we see that the two lines intersect -- and we can start to think about what it means to intersect. Essentially, on the path from start to end, they go through each other.
This intuitive definition can hint at a solution. If the starting x points pass each other when going to the ending x points, and the starting y points pass each other while going to the ending y points, that would seem to suggest that the two lines intersect. While in English that seems intuitive, let's think about what we mean by 'starting', passing and ending.
It turns out to be really hard to define starting and ending, but look again at pic1 and pic2, and try to think about how we can define starting and then see if something else passes.
Well, what starts to come out is starting and ending don't actually matter; we can choose either point and then see if we pass (or arrive at) the range of x and the range of y values of line2. If we do, we intersect. If we don't then we don't intersect.
We can code this up as:
bool intersection(struct point * start1, struct point * start2, struct point * end1, struct point * end2){
/* If both x values of line2 are to the left or both
* are to the right of line1's x values,
* lines cannot intersect. */
if ((start2->x <= start1->x && start2->x <= end1->x &&
end2->x <= start1->x && end2->x <= end1->x) ||
(start2->x >= start1->x && start2->x >= end1->x &&
end2->x >= start1->x && end2->x >= end1->x))
return(false);
/* If both y values of line2 are above or both are
* below line1's y values, lines cannot intersect. */
if ((start2->y <= start1->y && start2->y <= end1->y &&
end2->y <= start1->y && end2->y <= end1->y) ||
(start2->y >= start1->y && start2->y >= end1->y &&
end2->y >= start1->y && end2->y >= end1->y))
return(false);
/* Otherwise, lines must intersect */
return true;
}
Let's try this with our test examples in pic 1 and pic 2 and see if this works. They do!
However, there are two major bugs in this code. See if you can find them; we'll get to them tomorrow.
/* Please let me know if you find bugs (other than the two that are part of this problem). Thank you, Noah */
Code WorkOut of the Day -- Daily exercises for programmers looking for jobs, or just to keep sharp with skills and have fun. I give talks, like this: https://youtu.be/NpvTE7GlXSM for people looking for jobs, or groups of programmers preparing for M&A tech HR due diligence. Follow us on twitter: @codewod
How to
When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!
No comments:
Post a Comment