Intersection
Point of intersection of lines
a1, b1, c1 - coefficients of the first line,
a2, b2, c2 - coefficients of the second line,
x, y - intersection point.
\(x = {-(c1 \cdot b2 - c2 \cdot b1) \over (a1 \cdot b2 - a2 \cdot b1)} \\ y = {-(a1 \ cdot c2 - a2 \cdot c1) \over (a1 \cdot b2 - a2 \cdot b1)} \)
We already know how to check lines for intersection (they are not parallel), and find their point of intersection.
Now let's learn how to do this with segments.
First, let's learn how to simply check them for intersection.
Segments intersect if the ends of one are on opposite sides of the other and vice versa (this is easily checked by the cross product). The only case when this will not work - the segments lie on one straight line. For it, you need to check for the intersection of the so-called. bounding box (bounding box of the segment) - check for the intersection of the projection of the segments on the X and Y.
axes.
Now that we know how to check segments for intersection, let's learn how to find the point (or segment) of their intersection:
- if they do not intersect, then it is clear that such a point does not exist;
- otherwise, we will construct straight lines on which these segments lie.
If they are parallel, then the segments lie on the same line, and we need to find the intersection segment - from the maximum of the left borders of the segments to the minimum of the right borders (the point is less than the other point, if it is to the left, in case of equality X-coordinates - if it is lower).
If the lines are not parallel, then find the point of their intersection and return it.