This article will explain how to calculate intersection between two line segments.

First, let us define our 2 lines segments. A line segment is usually indicated as two points. We will define our 1st line as having the s point \(\dot{p_{s}}\) and the e point \(\dot{p_{e}}\). We will define our 2nd line with \(\dot{q_{s}}\) and \(\dot{q_{e}}\) as its s and e point respectively.

Now, there are many ways to find the intersection between two lines, depeing on what mathemetical formula of a line we want to use. For this article, we will use the parametric equation of the line. So our two lines will be:

$$ \dot{p'} = \dot{p_{s}} + p_{t}(\dot{p_{e}} - \dot{p_{s}}) $$ $$ \dot{q'} = \dot{q_{s}} + q_{t}(\dot{q_{e}} - \dot{q_{s}}) $$

You might recognize that this is simply a linear interpolation function. Notice the scalar \(p_{t}\) (and similarly \(q_{t}\)). If \(p_t\) is 0, \(\dot{p'}\) would be the start point of the line \(\dot{p_{s}}\), and when \(p_t\) is 1, \(\dot{p'}\) would be the end point of the line \(\dot{p_{e}}\). Note that if \(p_t > 1\) or \(p_t < 0 \), then \(\dot{p'}\) will not be on the line segment (this will be relevant)

For bevity, let's redefine \(\dot{p_{e}} - \dot{p_{s}}\) and \(\dot{q_{e}} - \dot{q_{s}}\) to \(\vec{p_v}\) and \(\vec{q_v}\) respectively, where 'v' means vector.

To find the point of intersection, we need to find \(p_{t}\) and \(q_{t}\) such that \(\dot{p'}\) and \(\dot{q'}\) are the same. That is:

$$ \dot{q_{s}} + q_{t}(\vec{q_{v}}) = \dot{p_{s}} + p_{t}(\vec{p_{v}}) $$

Since we are working in at least 2 or more dimensions (point of intersection does not make sense in 1D space), this means that each point or vector in our equation has at least two components (i.e. minimally \(x\) and \(y\)). We can then form at least two system of equations:

$$ q_{sx} + q_{t}q_{vx} = p_{sx} + p_{t}p_{vx} $$ $$ q_{sy} + q_{t}q_{vy} = p_{sy} + p_{t}p_{vy} $$

Two system of equations and two unknowns \(p_t\) and \(q_t\). We solve them accordingly.

Here, we solve using Substitution method. First, express one of the equation in terms of \(p_t\). We will use the \(x\) one:

$$ p_{t} = \frac{q_{sx} + q_{t}q_{vx} - p_{sx}}{p_{vx}} $$

Substitute \(p_t\)'s formula into the other equation, in this case the \(y\) one. Then solve to \(q_t\):

$$ q_{sy} + q_{t}q_{vy} = p_{sy} + p_{t}p_{vy} $$ $$ q_{sy} + q_{t}q_{vy} = p_{sy} + \frac{q_{sx} + q_{t}q_{vx} - p_{sx}}{p_{vx}} p_{vy} $$ $$ q_{sy} + q_{t}q_{vy} = p_{sy} + \frac{q_{sx}p_{vy} + q_{t}q_{vx}p_{vy} - p_{sx}p_{vy}}{p_{vx}} $$ $$ q_{sy} + q_{t}q_{vy} = \frac{p_{sy}p_{vx} + q_{sx}p_{vy} + q_{t}q_{vx}p_{vy} - p_{sx}p_{vy}}{p_{vx}} $$ $$ p_{vx}(q_{sy} + q_{t}q_{vy}) = p_{sy}p_{vx} + q_{sx}p_{vy} + q_{t}q_{vx}p_{vy} - p_{sx}p_{vy} $$ $$ p_{vx}q_{sy} + q_{t}q_{vy}p_{vx} = p_{sy}p_{vx} + q_{sx}p_{vy} + q_{t}q_{vx}p_{vy} - p_{sx}p_{vy} $$ $$ q_{t}q_{vy}p_{vx} = p_{sy}p_{vx} + q_{sx}p_{vy} + q_{t}q_{vx}p_{vy} - p_{sx}p_{vy} - p_{vx}q_{sy} $$ $$ q_{t}q_{vy}p_{vx} - q_{t}q_{vx}p_{vy} = p_{sy}p_{vx} + q_{sx}p_{vy} - p_{sx}p_{vy} - p_{vx}q_{sy} $$ $$ q_{t}(q_{vy}p_{vx} - q_{vx}p_{vy}) = p_{sy}p_{vx} + q_{sx}p_{vy} - p_{sx}p_{vy} - p_{vx}q_{sy} $$ $$ q_{t} = \frac{p_{sy}p_{vx} + q_{sx}p_{vy} - p_{sx}p_{vy} - p_{vx}q_{sy}}{q_{vy}p_{vx} - q_{vx}p_{vy}} $$

Whew! Now all we have to do is to sub \(q_{t}\) back into the first formula to find \(p_t\) (remember that \(q_t\) is now known):

$$ p_{t} = \frac{q_{sx} + q_{t}q_{vx} - p_{sx}}{p_{vx}} $$

Now that we know \(p_t\) and \(q_t\), we can use substitute them back into our initial parametric line equations

$$ \dot{p'} = \dot{p_{s}} + p_{t}(\dot{p_{e}} - \dot{p_{s}}) $$ $$ \dot{q'} = \dot{q_{s}} + q_{t}(\dot{q_{e}} - \dot{q_{s}}) $$

Both should give the same results, so if you are implementing this, you only need to choose either formula.

Wait, does that mean that we only need to find either \(q_t\) or \(p_t\), not both? Not neccesarily. Recall what I mentioned earlier: Note that if \(p_t > 1\) or \(p_t < 0 \), then \(\dot{p'}\) will not be on the line segment. The same goes for \(p_t\) and \(\dot{q'}\).

This means that to ensure that our intersection point is within our line segments, we have to check that both \(p_t\) and \(q_t\) are \(>= 0\) and \(<= 1\)!

There is one more caveat to take note. Recall our formula for \(q_t\):

$$ q_{t} = \frac{p_{sy}p_{vx} + q_{sx}p_{vy} - p_{sx}p_{vy} - p_{vx}q_{sy}}{q_{vy}p_{vx} - q_{vx}p_{vy}} $$

Note that there exists a case where \(q_{vy}p_{vx} - q_{vx}p_{vy} = 0\) , in which \(q_t\) becomes an undefined value. So what's the signifance of that?

We can disect the formula like so to better understand some of its properties:

$$ q_{vy}p_{vx} - q_{vx}p_{vy} = 0 $$ $$ q_{vy}p_{vx} = q_{vx}p_{vy} $$ $$ \frac{q_{vy}}{q_{vx}} = \frac{p_{vy}}{p_{vx}}$$

Turns it turns out that when \(q_{vy}p_{vx} - q_{vx}p_{vy} = 0\), it means that the gradient of the \(\vec{p_v}\) is the same as \(\vec{q_v}\), which means that they are either parallel or at least one of them is a zero vector

Check out the interactive visualization below. The purple line represents the line \(p\) while the orange line represents the line \(q\). The intersection of the two lines is represented with either a green circle, which indicates that the intersection point is within both line segments, or a red circle, which indicates otherwise.

Feel free to drag the start and end point of the lines and observe the intersection point as well as the \(p_t\) and \(q_t\) values; if either values are \(<0\) or \(>1\), then the intersection point is not within the line segments.