[Math] finding the intersection of two line segments in 2d (with potential degeneracies)

Question

I am trying to write an algorithm that finds the intersection of two line segments in the plane. The line segments are given as pairs of points, which I'm writing as $C_1$ and $C_2$, where $C_1 = (P_1, Q_1) = (p_{1x}, p_{1y}), (q_{1x}, q_{1y})$ and similarly for $C_2$. This question goes a little deeper than other questions I have seen on this topic.

Now, I have written the intersection as a system of equations:
$$ p = t_1 P_1 + (1-t_1)Q_1 = t_2 P_2 + (1-t_2)Q_2.$$

In matrix form, this system is given by

$$
\left(\begin{array}{cc}d_{1x} & d_{2x} \\ d_{1y} & d_{2y} \end{array}\right)
\left(\begin{array}{r}t_1 \\ -t_2\end{array}\right)
=
\left(\begin{array}{c}dq_{x} \\ dq_{y}\end{array}\right)
$$
where
$$
D_i = Q_i – P_i
$$
and
$$
Dq = Q_2 – Q_1.
$$

Now, if this system has a solution, then the solution satisfies
$$
\Delta \left(\begin{array}{c} t_1 \\ -t_2 \end{array}\right)
=
\left(\begin{array}{cc} d_{2y} & -d_{1y} \\ -d_{2x} & d_{1x} \end{array}\right)
\left(\begin{array}{c}dq_{x} \\ dq_{y}\end{array}\right).\qquad(*)
$$
where $\Delta$ is the determinant of the matrix above. If $\Delta \neq 0$, then there is a unique solution that is easy to find.

My question is about the case where $\Delta = 0$. In this case, the two lines are parallel, and are either disjoint (in which case the intersection of the segments is empty), or coincident (in which case the intersection may be empty, a point, or a line segment, depending on the boundaries).

If they are coincident, then the left hand side of $(*)$ must be zero, so the right hand side must be zero as well. My question is this: if they are disjoint, must the rhs of $(*)$ be non-zero? I suspect this is true, and if it is, then my code will look nicer :). It has worked out that way in the few examples I've tried, but I can't find a proof.

Answer 1

You might look at the code I wrote for Computational Geometry in C, which discusses this question in detail (Chapter 1, Section 5). The code is available as SegSegInt from the links at that web site.

In a nutshell, I recommend a different approach, using signed area of triangles. Then comparing appropriate triples of points, one can distinguish proper from improper intersections, and all degenerate cases. Once they are distinguished, finding the point of intersection is easy.