Twisted Oak Studios

Determining exactly if/when/where a moving line intersected a moving point

posted by Craig Gidney on February 5, 2013

I try to include sample projects when I publish libraries. In the case of perishable collections, the sample project was actually a simple game based on cutting lines with the mouse pointer:

As part of writing the sample, I had to solve the problem of determining if, when, and where the mouse pointer was swept across a line (or vice versa). My usual reference for geometry algorithms didn’t contain a solution, so I developed one myself.

In this post I’ll be explaining an analytical solution to the problem. The solution is implemented in a small amount of source code (about 150 lines, counting comments and supporting methods/types), also available on github.

Destination

It turns out that “did the mouse pointer cut the moving line?” is one of those magical math problems that starts out with some relatively simple constraints, then appears to become quite complicated as you solve it, but then almost everything cancels or combines in the last few steps and you end up with something absurdly simple. (Then, when you go back to look over the solution, it turns out there was an easy path the whole time.)

For reference and motivation, I’m just going to dump the meat of the implementation right here, before explaining it. Underlined words are links to the corresponding code on github.

public static IEnumerable<Sweep> WhenLineSweepsPoint(LineSegment pathOfLineStartPoint,
                                                     LineSegment pathOfLineEndPoint,
                                                     Point point) {
var a = point - pathOfLineStartPoint.Start;
var b = -pathOfLineStartPoint.Delta;
var c = pathOfLineEndPoint.Start - pathOfLineStartPoint.Start;
var d = pathOfLineEndPoint.Delta - pathOfLineStartPoint.Delta;

return from t in QuadraticRoots(b.Cross(d), a.Cross(d) + b.Cross(c), a.Cross(c))
       where t >= 0 && t <= 1
       let start = pathOfLineStartPoint.LerpAcross(t)
       let end = pathOfLineEndPoint.LerpAcross(t)
       let s = point.LerpProjectOnto(new LineSegment(start, end))
       where s >= 0 && s <= 1
       orderby t
       select new Sweep(timeProportion: t, acrossProportion: s);
}

I don’t know about you, but the fact that the above code solves the problem amazes me. It seems too straightforward, and yet too unrelated. Shouldn’t there be, like, corner cases? Plus, where did those simple cross products come from? How does feeding them into a quadratic polynomial help? This… is going to need to be explained.

Intuition

Lets start by considering some of the cases we might encounter, in order to get an intuitive feel for the problem. The animation below shows several different possible line motions:

Simple: both endpoints move at the same velocity, and only along the line’s normal vector.
Sideways: a degenerate case where the line is moving along its own length.
Raise: one endpoint moves horizontally while the other moves vertically (‘raising’ and lowering the line).
Dive: one endpoint moves diagonally (‘diving’ through the middle) while the other moves vertically.

Various sweep cases

Notice that a line can sweep a point 0, 1, or 2 times as its endpoints move at a constant rate from one position to another. The ‘Raise’ case conveniently contains all three possibilities. This, intuitively, is why the solution involves a quadratic equation (which can have 0, 1, or 2 distinct real roots).

Another useful realization is that some of the cases, like the line moving at a constant rate or standing still, will correspond to degenerate quadratic equations where the highest order coefficient is zero (i.e. $0 x^2 + b x + c = 0$ or even $0 x^2 + 0 x + c = 0$ ). We need to include these sorts of cases in the tests.

Model

In order for a line segment from $p$ to $q$ to contain a point $c$ , two conditions must be satisfied. First, the ‘offset’ vector from $p$ to $c$ must be parallel to the ‘delta’ vector from $p$ to $q$ . We can represent this mathematically by requiring that their cross product be zero: $(c-p) \times (q-p) = 0$ . This guarantees that $c$ is on the line you get by extending the line segment in both directions (or that you have a degenerate single-point line segment). Second, the scalar projection $s$ of the offset vector onto the delta vector must be in the right range: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . This guarantees that $c$ is not past either of the segment’s end points.

As time goes from $t=0$ to $t=1$ , our line segment will have swept a point $c$ if and only if there is a time $t$ where the current line segment contains $c$ . Because the endpoints of our line segment are moving at a constant rate, the path they follow is also a line segment. An endpoint moving from $p_0$ to $p_1$ will be at the linearly interpolated point $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ at time $t$ . Note that I’m going to abbreviate $p_1-p_0$ as $p_d$ to save space. Plugging our moving points into our ‘line segment contains point’ formulas tells us that we must find $t$ satisfying $0 \leq t \leq 1$ and $(c - (p_0 + p_d \cdot t)) \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ and $0 \leq s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2} \leq 1$ .

Note that “some cross product must equal 0″ is not the only way to frame the problem. It also makes sense to think of it as finding a $t$ and $s$ , both in the range $[0, 1]$ , such that $c$ is the result of lerping both endpoints across their path by $t$ and then lerping between the endpoints by $s$ . Mathematically, that means $c = lerp(lerp(p_0, p_1, t), lerp(q_0, q_1, t), s)$ . The variables $t$ and $s$ roughly correspond to “when” and “where” an intersection occurs. However, it’s harder to solve the problem in this form, because $t$ isn’t initially isolated, so I’ll be using the cross product framing (unlike I did the first time…).

Solution

The cross product and dot product have some very nice properties that will make it easier to isolate $t$ . First, they distribute addition, meaning $u \times (v + w) = u \times v + u \times w$ and $u \cdot (v + w) = u \cdot v + u \cdot w$ . Second, scaling can be done before or after either product, meaning $(c \cdot u) \times v = c \cdot (u \times v)$ and $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , where $c$ is a real number. Finally, the dot product is commutative, meaning $u \cdot v = v \cdot u$ , whereas the cross product is anti-commutative, meaning $u \times v = -v \times u$ .

Applying this product knowledge, and using some hindsight to know to treat particular sub-expressions as individual variables, we can transform our cross-product-is-zero equation into a quadratic equation:

$\begin{align*} 0 &=(c - (p_0 + p_d \cdot t)) \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) \\&= ((c - p_0) - p_d \cdot t) \times ((q_0 - p_0) - (q_d - p_d) \cdot t) \\&= (a + b \cdot t) \times (c + d \cdot t) \\&\;\;\;\;\;\;\;\;where\;\; a = c - p_0 \\&\;\;\;\;\;\;\;\;where\;\; b = -p_d \\&\;\;\;\;\;\;\;\;where\;\; c = q_0 - p_0 \\&\;\;\;\;\;\;\;\;where\;\; d = -(q_d - p_d) \\&= a \times c + a \times d \cdot t + b \times c \cdot t + b \times d \cdot t \cdot t \\&= t^2 \cdot (b \times d) + t \cdot (a \times d + b \times c) + (a \times c) \end{align*}$

(This is hilariously simpler than the route I took the first time.)

Ah, now it’s clear where the form of the code solution came from. We started with a cross product equaling zero (asserting that the vector from the line to the point was parallel with the line) and had to split up the product in order to isolate sums of terms involving different powers of $t$ . This naturally yields a quadratic equation with coefficients involving cross products. Neat!

Note that this is a very “sturdy” equation, because we never assumed anything about the vectors or scalars along the way. For example, we never divide (or implicitly cancel) by a variable, so we haven’t introduced any lurking non-zero conditions.

With the simplified equation, determining the possible values of $t$ is just standard “solve quadratic polynomial” stuff. We have to handle corner cases with zeroes, which makes the code a bit more complicated, but it’s just boring case by case stuff so I’ll just link to it.

Once we know a possible value of $t$ , we can find out exactly where the collision occurred by using the plug-t-into-line-segment-point-containment formula mentioned a ways back: $s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2}$ . I call this formula the “lerp projection” of $c$ onto the line at time $t$ , because it returns the proportion $s$ to lerp by, from the line’s start point to its end point, in order to get $c$ back. It’s a handy little method to extract:

public static double LerpProjectOnto(this Point point, LineSegment line) {
    var b = point - line.Start;
    var d = line.Delta;
    return (b * d) / (d * d); // when d == 0, result is +-infinity or NaN
}

Finally, once we have $t$ and $s$ , we need to check that they’re in the range $[0, 1]$ . If $t$ is out of range then the collision won’t occur during the current time step. If $s$ is out of range then the collision will occur on the extended line, but not the line segment. Since $s$ and $t$ describe how much to lerp in order to find when/where the collision occurred, it’s also useful information to return to the caller.

Generalizing

An important detail I haven’t mentioned yet is that a moving mouse pointer obviously doesn’t correspond to a point. Luckily, we can just cancel out the mouse pointer’s motion over the last time step (assuming it is linear) by deducting it from the line segment’s motion. Not only does this reduce the system to a solvable one, but the resulting $t$ and $s$ values are valid without any sort of inverse transformation. Usage looks like this:

// time goes from t0 to t1
// line segment endpoint 1 moves from p0 to p1
// line segment endpoint 2 moves from q0 to q1
// point moves from c0 to c1
var results = from hit in WhenLineSweepsPoint(new LineSegment(p0 - c0, p1 - c1),
                                              new LineSegment(q0 - c0, q1 - c1),
                                              new Point(0, 0))
              let hitPos = new LineSegment(c0, c1).LerpAcross(hit.TimeProportion)
              let hitTime = t0 + (t1-t0)*hit.TimeProportion
              select new { p = hitPos, t = hitTime }
foreach (var result in results) {
    System.Diagnostics.Debug.WriteLine(string.Format("Hit at p={0}, t={1}", result.p, result.t);
}

A potential complication is degenerate line segments that have no length (where both endpoints are equal). The code does not explicitly handle this case, but will act as if cutting a line-that-is-actually-a-point is impossible. The computation of $s$ , if it’s reached, will divide by zero. The result (either -infinity, +infinity, or NaN) will fail the range check.

Another aspect I haven’t covered is the ‘cut angle’. In the animation showing the various cases, the red cuts are oriented by lerping between the velocities of the two endpoints by $s$ (when the resulting velocity is 0, a random angle is chosen). But I’ve also used alternate approaches like “the cut angle is the point’s velocity”. Basically, it’s a case of using whatever looks good and feels natural instead of trying to figure out the true meaning of “cut angle”.

Summary

This problem becomes trivial as soon as you apply some knowledge from linear algebra. I guess that’s not too surprising, since linear algebra (and polynomials) show up everywhere, especially in geometry.

A natural generalization of this problem is to include thicknesses. Lines drawn on screens are not infinitely thin, after all. Having a thickness is also a good way to reduce the effect of floating point errors rounding in different directions during different time steps. Another useful change would be the ability to handle parabolic paths, since game objects are often in free fall. On the other hand, I guess it’s probably easier to just treat ‘thick lines’ as polygons with constant-speed time steps.

—

Discuss on Reddit

—

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.