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.
Comments (1)
Boyko Bantchev on 8 Jun 2019, 3:56 p.m.
It is possible to do better, e.g. avoiding computing the point of intersection of the lines AB and CD when it does not belong to the respective segments. There are other benefits as well. It all amounts to making proper use of the cross product.
For any points X, Y, Z let us denote [XYZ] = XY×XZ (= XY×YZ), where × is the 2D cross product. (Thus [PQR] is twice the oriented area of ∆PQR.)
Consider [ABC] and [ABD]. If the two products are of the same arithmetic sign, then C and D are in the same half-plane w.r.t. the line AB, therefore no common point of the segments AB and CD exists. If [ABC] and [ABD] are of opposite signs, or if exactly one of them is 0, then the segments AB abd CD have a common point if and only if [ACD] and [BCD] are not of the same sign (note that they cannot be both 0, as that would also imply [ABC] = [ABD] = 0).
If we already know that the point of intersection P exists, we are but one step away from finding P itself, using P = A+t.AB. For this it suffices to figure out that t = [ACD]/(AB×CD) and that we can avoid computing AB×CD since the latter product equals [ACD]-[BCD]. (Note that we have already computed both [ACD] and [BCD].) Thus finding t requires no more than a subtraction and a division of known numbers.
Worth pointing out is that we need a division operation only to actually find the point of intersection – when we are sure that there is one. Thus, if the coordinates of the points are integer, we can do an exact arithmetic and not resort to floating-points only to find out whether a point of intersection exists. We are being both precise and efficient through lazyness! And of course, we can also avoid division when any of [ABC], [ABD], [ACD], [BCD] is 0. E.g., [ABC] = 0 means that C is on the line AB, hence if there is a common point of the segments AB and CD, it must be C.
The only case not considered above is [ABC] = [ABD] = 0, i.e. the lines AB and CD coincide. Here, a unique common point of the two segments exists if and only if one of A and B coincides with one of C and D and the segments are oppositely directed. E.g., if A ≡ C, then there must be AB·CD < 0 (· being the scalar product).
\