Line-line intersections


Jan. 26, 2016

Introduction

A common task in computer graphics is to find whether two line segments intersect, and if they do, where. Line segments are defined by a pair of points in 2D or 3D space.

The task can be split into three parts:

  • For each pair of points get an equation for a line that passes through both points.
  • Solve the simultaneous equations to see where the two lines are equal
  • If there is a solution (i.e. the lines are not parallel), test whether the intersection point is on both line segments (not just the lines).

Click and drag the line endpoints. This image was built with my InteractiveSVG.js

Equations of line

Slope-intercept form

There are several ways to get an equation for a line. The most common is probably slope-intercept form:

$\qquad y = mx + b$

where $m$ is the gradient of the line and $b$ is where the line intersects the $y$-axis.

One problem with slope intercept form is that it doesn't work for vertical lines: a vertical line has an undefined gradient and doesn't intercept the $y$-axis. It's also a bit tricky to define a line segment. So we need another type of equation to represent the lines.

Parameterised lines

A useful way to define a line segment is to parameterise a line, which means introduce a parameter, normally $t$, which defines how far along the line you are. For example, we can define an equation:

$\qquad P = (1 - t)A + tB$

For every value of $t$ you'll get a point along the line $AB$. For example,

  • When $t=0$, $P=A$
  • When $t=1$, $P=B$
  • When $t=0.5$, $P$ is halfway between $A$ and $B$

This is useful for line segments since we can say we're only interested in points where $0 \geq t \geq 1$. We can also rearrange the equation to:

$\qquad P = A + (B - A)t$

This is perhaps clearer to understand. It says that we start at point $A$ and move along a vector that starts at $A$ and points to $B$, using $t$ as the proportion of the vector.

The Pixar lesson on Environment Modeling explains the concept more clearly.

Solving simultaneous equations

Now we have a good way to represent lines, let's calculate where they cross (if they do). Start with four points, $A$, $B$, $C$ and $D$, where $A$ has coordinates $(A_x, A_y)$, $B$ has coordinates $(B_x, B_y)$, and so on. We want to find whether line segment $\overline{AB}$ intersects with line segment $\overline{CD}$.

We start by getting the parameterised equation for each line:

$\qquad \begin{align} P_1 &= A + (B - A)t \\ P_2 &= C + (D - C)s \end{align}$

We want to find a point that lies on both lines, so we want to find a value for $t$ and $s$ where the equation gives the same result. So we set the equations equal to one another:

$\qquad A + (B - A)t = C + (D - C)s$

This equation deals with points, but we can split it into two equations dealing with the coordinates of the points:

$\qquad \begin{align} A_x + (B_x - A_x)t &= C_x + (D_x - C_x)s \\ A_y + (B_y - A_y)t &= C_y + (D_y - C_y)s \end{align}$

Now we have two equations in two unknowns ($t$ and $s$), so we can solve them. First, we rearrange them:

$\qquad \begin{align} (B_x - A_x)t &= C_x - A_x + (D_x - C_x)s \\ (B_y - A_y)t &= C_y - A_y + (D_y - C_y)s \end{align}$

It might be tempting to divide each side of the first equation by $(B_x - A_x)$ and each side of the second equation by $(B_y - A_y)$, to get them both in terms of $t$. However, then we would be left with the same problem that slope-intersection form gives, namely the equation is undefined when $\overline{AB}$ is vertical (since we would be dividing by $B_x - A_x$, which would be $0$).

So instead, we multiply the first equation by $(B_y - A_y)$, and the second equation by $(B_x - A_x)$:

$\qquad \begin{align} (B_x - A_x)(B_y - A_y)t &= (B_y - A_y)(C_x - A_x + (D_x - C_x)s) \\ (B_x - A_x)(B_y - A_y)t &= (B_x - A_x)(C_y - A_y + (D_y - C_y)s) \end{align}$

The equations are getting a bit messy, so now would be a good time to make some simplifications. Let's define some new constants:

$\qquad \begin{align} dx_1 &= B_x - A_x \\ dy_1 &= B_y - A_y \\ dx_2 &= D_x - C_x \\ dy_2 &= D_y - C_y \\ dx_3 &= C_x - A_x \\ dy_3 &= C_y - A_y \\ \end{align}$

Notice that $(dx_1, dy_1)$ is a vector for line segment $\overline{AB}$, $(dx_2, dy_2)$ is a vector for line segment $\overline{CD}$, and $(dx_3, dy_3)$ is a vector from $A$ to $C$.

We can now write the equation as:

$\qquad \begin{align} dx_1 \cdot dy_1 \cdot t &= dy_1(dx_3 + dx_2 \cdot s) \\ dx_1 \cdot dy_1 \cdot t &= dx_1(dy_3 + dy_2 \cdot s) \end{align}$

The left-hand side of each equation is equal, so we can set the right-hand sides to be equal:

$\qquad \begin{align} dy_1(dx_3 + dx_2 \cdot s) &= dx_1(dy_3 + dy_2 \cdot s) \\ dy_1 \cdot dx_3 + dy_1 \cdot dx_2 \cdot s &= dx_1 \cdot dy_3 + dx_1 \cdot dy_2 \cdot s \\ (dy_1 \cdot dx_2 - dx_1 \cdot dy_2) \cdot s &= dx_1 \cdot dy_3 - dy_1 \cdot dx_3 \\ s &= \frac{dx_1 \cdot dy_3 - dy_1 \cdot dx_3}{dy_1 \cdot dx_2 - dx_1 \cdot dy_2} \end{align}$

Now we have an equation to find the value for $s$, how far along $\overline{CD}$ an intersection is.

Cross product

Our equation has similar terms in the numerator and denominator. In both cases it is the $x$ term from one vector multiplied by the $y$ term from another, and subtracted from the $y$ term from the first vector multiplied by the the $x$ term from the second. This operator is the the 2D cross product of the two vectors.

Notice too that the denominator of our equation is $dy_1 \cdot dx_2 - dx_1 \cdot dy_2$. We have gone to quite a lot of effort to avoid having zero in the denominator - will this expression ever equal zero, and if so when?

$\qquad \begin{align} dy_1 \cdot dx_2 - dx_1 \cdot dy_2 &= 0 \\ dy_1 \cdot dx_2 &= dx_1 \cdot dy_2 \\ \frac{dy_1}{dx_1} &= \frac{dy_2}{dx_2} \end{align}$

So our $s$ term will be undefined when gradient of $\overline{AB}$ equals the gradient of $\overline{CD}$. That makes sense because when the gradients are equal, the lines are either parallel or aligned. Either way, there is no meaningful intersection point.

Now we have calculated $s$, we first check whether $0 \geq s \geq 1$. If not, then the "intersection" occurs on a point not on $\overline{CD}$ (but it is on the line that passes through points $C$ and $D$). Then we can plug $s$ into either of the following equations to find $t$:

$\qquad \begin{align} A_x + (B_x - A_x)t &= C_x + (D_x - C_x)s \\ A_y + (B_y - A_y)t &= C_y + (D_y - C_y)s \end{align}$

The final answer

Note that if $\overline{AB}$ is vertical, then $(B_x - A_x) = 0$, so in the first equation, the $t$ term disappears; in that case, use the second equation. Likewise, if the line in horizontal, you will have to use the first equation.

Once you have $t$, you check whether $0 \geq t \geq 1$, and if it is, then you do have an intersection. Finally, you can plug either $s$ or $t$ into one of the parameterised line equations to find the coordinates of the intersection point.

Leave a comment

cancel reply