# finding the intersection of two line segments in 2d (with potential degeneracies)

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.

-
For those looking for code, my (Java) implementation is available here. See the "intersect" method. –  mdgeorge Jan 14 '13 at 15:39

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.

-
OT: a nice surprise to see you on math.se! I recently studied some of your work, frustrated by the fine points of doing computational geometry in floating point... –  WimC Jan 13 '13 at 17:28
Thanks, I took a quick look at the code, but I found it a bit impenetrable so far. I'll see if I can track down your book. –  mdgeorge Jan 14 '13 at 4:07
The code is explained in the book. The code comments do not suffice; sorry! –  Joseph O'Rourke Jan 15 '13 at 1:08

After sleeping on it, I realized that my conjecture is false, and it's kind of easy to come up with a counterexample. For example: $$\begin{array}{ccccc} & & (1,1) & - C_1\!- & (2,1) \\ & & & & \\ (0,0) & - C_2 \!- & (1,0) & & \\ \end{array}$$ In this case, $Dq = (1,1)$, while both $D_1$ and $D_2$ are $(1,0)$. So the right hand side of $(*)$ is $$\left(\begin{array}{cc} 0 & 0 \\ -1 & 1 \end{array}\right) \left(\begin{array}{c} 1 \\ 1 \end{array}\right) = \left(\begin{array}{c} 0 \\ 0 \end{array}\right)\!,$$ but the lines are clearly not collinear.

So, you must do a different set of computations to handle the degenerate case, based on area as Joseph suggests, or using the observation that the lines coincide if the slope of the line between the $Q_i$ is the same as the slopes of the $P_iQ_i$ lines (which is what I did). I think the equations come out the same either way.

-