0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ DO you mean analitically? $\endgroup$ Jan 28, 2021 at 20:57
  • $\begingroup$ @TitoEliatron Not sure what you mean by analytically? $\endgroup$
    – BenLewis
    Jan 28, 2021 at 20:58
  • $\begingroup$ You can rotate the coordinate frame so that the line coincides with the $x$-axis, then just look to see whether the $y$ coordinates of the end points are of opposite signs, which would be a quick and dirty way of doing it. $\endgroup$ Jan 28, 2021 at 20:59
  • $\begingroup$ You can look if the line $L$ and the line containing the segment intersect. If they don't, segment neither does. If they do, you can look if the intersection point is in the segment or not. $\endgroup$
    – R.V.N.
    Jan 28, 2021 at 21:11
  • $\begingroup$ @R.V.N. Good idea, thanks! $\endgroup$
    – BenLewis
    Jan 28, 2021 at 21:14

1 Answer 1

0
$\begingroup$

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°$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.