Week 7

How to check if a point is inside the polygon/shape

Find all collinear points in a given set

How to check if two given line segments intersect?

Calculation of intersections between line segments:

an easier way of understanding it is through solving a system of equations. Firstly look at lines generally and then cut segments from them. Below I use notations for given segments ((x1, x2), (y1, y2)) and ((x3, x4), (y3, y4)).

1. Check if any of the lines is vertical (x1 == x2 or x3 == x4).
2. a. If both are vertical and x1 != x3, then no intersection.
3. b. If both are vertical and x1 == x3, check if (y1, y2) and (y3, y4) overlap.
4. c. If only one is vertical (say, first one), then build the equation of the second line (as outlined below), find the point where two lines intersect (by substituting x1 into the equation of the second line) and check if this point is within both segments (similar to step 5).
5. d. If not, proceed.
6. Use the points coordinates to build lines equations in form y = a*x + b (like here).
7. a1 = (y2-y1)/(x2-x1)
8. b1 = y1 - a1*x1
9. a2 = (y4-y3)/(x4-x3)
10. b2 = y3 - a2*x3
11. Check if lines are parallel (same slope a). If yes, check if they have same intercept b. If yes, check if 1D segments (x1, x2) and (x3, x4) overlap. If yes, your segments do overlap. The case when lines are parallel can be ambiguous. If they overlap, you can consider it as an intersection (it even can be one point if their ends are touching), or not. Note: if you are working with floats it would be a bit trickier, I reckon you would want to ignore this. In case you have only integers checking if a1 = a2 is equivalent to:
12. if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3))
13. If lines are not parallel. The point of intersection is equivalent to a solution of a system of equations representing the two lines. Really, y = a1*x + b1 and y = a2*x + b2intersecting basically means that both of these equations hold. Solve this system by equating the two right sides and it will give you the intersection point. In fact, you need only xcoordinate of the intersection (draw it and you'll see why):
14. x0 = -(b1-b2)/(a1-a2)
15. Last step is to check if the intersection point x0 lies within both segments. That is, min(x1, x2) < x0 < max(x1, x2) and min(x3, x4) < x0 < max(x3, x4). If yes, your lines do intersect!