criterion for two line segments intersecting

Question

I have two line segments $[(x_1, y_1),(x_2, y_2)] $ and $[(x_3, y_3),(x_4, y_4)] $ and I want to know if they intersect.

My current algorithm tries the following:

• the line $[(x_1, y_1),(x_2, y_2)] $ is determined by $\boxed{f(x,y) = \frac{y - y_1}{x - x_1} - \frac{y_2 - y_1}{x_2 - x_1} = 0}$.
• I reasoned that if $y = mx+b$ is my line, I want a point such that $y > mx+b$ and one such that $y < mx+b$.
• I want to check if that $f(x,y)$ has opposite signs if I set it on $(x_3,y_3)$ and $(x_4, y_4)$. So the criterion I check right now is: $$ \frac{f(x_3,y_3)}{|f(x_3,y_3)|}\; \frac{f(x_4,y_4)}{|f(x_4,y_4)|} = -1 $$ Unfortunately in my visualization, I still see line segments intersecting.

Is there something wrong with my algorithm? What is a correct way to check that two line segments intersect?

Answer 1

You need to know about the orientation test.

For any three points, compute the determinant

$$\Delta_{123}=\left| \begin{array}{ccc} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{array} \right|.$$

This is twice the signed area of the triangle $123$. When it is $0$, it tells you that the three points are aligned. Otherwise, it tells you on what side of the line joining two points the third lies.

In your case, there is an intersection if $1$ and $2$ are on either sides of $34$, while $3$ and $4$ are on either sides of $12$: $$(\Delta_{134}>0)\ne(\Delta_{234}>0)\land(\Delta_{123}>0)\ne(\Delta_{124}>0).$$

It is up to you to decide what to do in cases of perfect alignments.

As an extra goodie, the $\Delta$'s can be used to compute the coordinates of the intersection. (Let $P$ be the intersection point, interpolated along the segment $P_1P_2$: $P=(1-t).P_1+t.P_2$; it is easy to show that $(1-t)\Delta_{134}+t\Delta_{234}=0$ and to find the value of $t$.)

Answer 2

The vector equation:

$$P_1 + \alpha * (P_2 - P_1) = P_3 + \beta * (P_4 - P_3)$$

where $P_1 = (x_1, y_1)$ etc., should have a solution in the unit square:

$$0 \le \alpha \le 1, 0 \le \beta \le 1$$

then these two segments $(P_1, P_2)$ and $(P_3, P_4)$ do intersect. However, there are many corner cases here (for example, $P_1 = P_2$ etc.). Also, you can get wrong answers because of the limited precision of your data representation in computer.