Vrftjkry

How to tell whether a semi straight line intersects with a line segment?

This is required because I am writing an algorithm to check if a given point lies inside or outside a polygon.

Update

Apparently semi straight line is also known by the name of ray.

Write the parametric equations of the full line (param. $t=0$ at the origin, and then positive for the part condidered) and that of the segment (param. $s=a$ at one end, $a<s=b$ at the other).

Determine the crossing point and check if $0 le t$ and $a le s le b$.

Let's say the line segment is between $vec{v}_1$ and $vec{v}_2$, and that the ray starts from $vec{o}$ in direction of $vec{d}$,
$$bbox{vec{v}_1 = left[begin{matrix}x_1\y_1end{matrix}right]} , quad
bbox{vec{v}_2 = left[begin{matrix}x_2\y_2end{matrix}right]} , quad
bbox{vec{o} = left[begin{matrix}x_0\y_0end{matrix}right]} , quad
bbox{vec{d} = left[begin{matrix}x_d\y_dend{matrix}right]}$$
We can describe the points on the line segment as a vector-valued function, $vec{p}(t)$
$$bbox{vec{p}(t) = (1 - t)vec{v}_1 + tvec{v}_2} , quad bbox{0 le t le 1}$$
Similarly, we can describe the ray as a vector-valued function $vec{r}(tau)$,
$$bbox{vec{r}(tau) = vec{o} + tau vec{d}}$$
Their intersection is obviously
$$bbox{vec{p}(t) = vec{r}(tau)}$$
Now, remember that those are actually vector-valued functions, so that is actually a system of two linear equations:
$$bbox{leftlbracebegin{aligned}
x_o + tau x_d &= (1 - t) x_1 + t x_2 \
y_o + tau y_d &= (1 - t) y_1 + t y_2 \
end{aligned}right.} , quad bbox{ 0 le t le 1, ; ; tau ge 0 }$$
This system has at most one solution,
$$bbox{leftlbracebegin{aligned}
displaystyle t &= frac{ y_d (x_1 - x_0) - x_d (y_1 - y_0)}{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
displaystyle tau &= frac{ x_0 (y_1 - y_2) + x_1 (y_2 - y_0) + x_2 (y_0 - y_1) }{ x_d (y_2 - y_1) - y_d (x_2 - x_1) } \
end{aligned}right.}$$
Note that they have the same divisor, which is zero if the ray and the line segment are parallel. You also need to verify that $0 le t le 1$ and $tau ge 0$ for the intersection to exist.

If there is an intersection, it is at $vec{p}(t) = ( (1-t)x_0 + t x_1 ,, (1-t)y_0 + t y_1 )$, which is equivalent to $vec{r}(tau) = ( x_0 + tau x_d ,; y_0 + tau y_d )$.

Note that although mathematically $(1-t) x_0 + t x_1 = x_0 + t (x_1 - x_0)$, the left side is more stable numerically. It means that if you use floating-point numbers, and $x_0$ and $x_1$ are vastly different in magnitude, the left side will still yield $x_0$ at $t=0$, and $x_1$ at $t=1$; but the right may not match $x_1$ at $t = 1$, because of the limited precision in floating-point numbers.

The reason I showed the explicit solution above, is that in the real world, the point in polygon test is better solved using a winding number algorithm.

The trick is that you only consider four directions, not any kind of angles:

You check each polygon edge in order. If the edge crosses the $x$ or $y$ coordinate of the test point, you check which side it does so. (In most cases, you only need to check the axis-aligned bounding box for the edge. In a very few cases, you need to check where the edge crosses the test point $x$ or $y$ coordinate, and in which order.)

Instead of angles as in degrees, you consider a full turn to be four quarters. A line segment can cross the test point $x$, $y$, or both. If a line segment crosses both, you need to determine which one it crosses first. Then, you only need to remember which axis/direction was crossed last. (If none, then the point is completely outside the polygon.) If the next crossing is counterclockwise from the last one, increase the winding; if the next crossing is clockwise, decrease the winding; repeated crossings of the same direction does not affect the winding.

If you calculated the crossings correctly, then winding will be an integer multiple of 4 (0, ±4, ±8, ±12, and so on). If the winding is 0, then the point is outside the polygon.

There are two common definitions for "inside" for self-intersecting polygons: odd-even and nonzero. Odd-even means that if the winding is an odd number of turns (here, not an integer multiple of 8), the point is inside; otherwise it is outside. Nonzero means that if the winding is nonzero, the point is inside. If you consider a pentagram drawn using five lines, the difference between the two definitions is whether the pentagon at the center of the pentagram is "inside" or not. In nonzero it is inside, in odd-even it is outside.