How do you check if a segment intersects a line?

Question

As the title says, how can you check if a line segments intersects an infinite line. Note that this is not line-line intersection, or segment-segment intersection.

For example, how can you check whether a segment $A$ or $B $ crosses line $L $ as shown in Fig.1.

Answer 1

Let the line segment endpoints be $\vec{p}_1 = (x_1 , y_1)$ and $\vec{p}_2 = (x_2 , y_2)$, and the line pass through points $\vec{p}_3 = (x_3 , y_3)$ and $\vec{p}_4 = (x_4 , y_4)$. Then, if and only if $$\Bigl( (\vec{p}_4 - \vec{p}_3) \times (\vec{p}_1 - \vec{p}_3) \Bigr) \Bigl( (\vec{p}_4 - \vec{p}_3) \times (\vec{p}_2 - \vec{p}_3) \Bigr) \le 0$$ does the line segment intersect the line. In Cartesian coordinate form, $$\Bigl( (x_4 - x_3)(y_1 - y_3) - (x_1 - x_3)(y_4 - y_3) \Bigr) \Bigl( (x_4 - x_3)(y_2 - y_3) - (x_2 - x_3)(y_4 - y_3) \Bigr) \le 0$$ The sign of the first multiplicand depends on which side $\vec{p}_1$ is to the line, and the sign of the second multiplicand depends on which side $\vec{p}_2$ is to the line. If the product is zero, $\vec{p}_1$ and/or $\vec{p}_2$ is on the line. If the product is negative, then the two points must be on different sides of the line.

If the two points are on different sides of the (infinitely long) line, then the line segment must intersect the line. If the two points are on the same side, the line segment cannot intersect the line.

Mathematically, this relies on the fact that the angle $\varphi$ between two vectors $\vec{a}$ and $\vec{b}$ fulfills $$\sin\varphi = \frac{\vec{a}}{\left\lVert\vec{a}\right\rVert} \times \frac{\vec{b}}{\left\lVert\vec{b}\right\rVert}$$ i.e. $$\left\lVert\vec{a}\right\rVert \left\lVert\vec{b}\right\rVert \sin\varphi = \vec{a} \times \vec{b} \tag{1}\label{G1}$$ where $\times$ is the 2D analog of vector cross product, $$(x_a, y_a) \times (x_b, y_b) = x_a y_b - y_a x_b$$ so that the sign of $\eqref{G1}$ corresponds to the sign of $\varphi$ when $-180° \lt \varphi \lt +180°$.