Finding Catmull-Rom Spline and Line intersection. Part 1: Brute-force

This was an issue I tackled for a while and ended up with a pretty neat optimized solution – at least so I thought at the time. As it turns out it’s completely useless in light of the matchematical approach I later implemented. Still it was a pretty nice try and makes for a good story on how a programmer vs. a mathematician would approach a problem. At the end it seems like I’m both. Lucky me.

Anyway this line of thinking (pun not intended) may actually be useful in other cases where you’re left without a pure mathematical approach.

Brute-force 101

So the problem is given. Assuming you don’t want to take a deep-dive in equations you’re left with one choice. That one’s actually fairly straightforward.

Let’s take all points of your Line and cross-reference it with all points of your Spline and see if they have anything in common. Or at least within a certain margin of error. Being a smart developer you chose a library that has already a built-in way to iterate these objects. Your code might look something like this:

for (float l = 0f; l <= 1f; l+= precision ) {
    linePoint = line.valueAt(l);
    for (float s = 0f; s <= 1f; s += precision) {
        splinePoint = spline.valueAt(s);
        if (linePoint.dst(splinePoint) < delta) return splinePoint;
    }
}

Precision and delta should be chosen carefully. You’d probably want to chose delta first to set a maximum inaccuracy. Then you need to set the precision so that you can actually find the data you’re looking for. This may be much harder than it first seems especially considering how loose some libraries play with precision.

And there you have it: a very low-effort solution that can actually work just fine for you.

complexity cut

Well, it did not quite work for me. If you need to do this more than once, let alone continuously in real-time the above solution will really start to push it.

Time to get creative!

… but first of all you can’t really better anything if you can’t measure it. Assuming your  Line has L points and yor Spline has S the above solution yields a complexity of O(L*S). Simplifying it to a common precision (N) it’s O(N^2). Now even if you don’t know much about the order of algorithms you should know that anything with an exponent is bad.

Given that we’re brute-forcing (i.e. trying all possibilities) we can’t make our algorithm’s complexity independent from the object’s complexity. But maybe we can ignore some possibilities along the way.

X-flat spline

Here comes the idea: let’s construct our Spline in a way that it is continuous on one axis. My setting is vertical so I chose X.

This will enable us to simplify things a lot. Take a random point. Take the first and last point of your Spline. Just by looking at the X coordinates you can tell if that point has no chance at all of being on the Spline (i.e. it’s not between the Spline’s ends). If it does you still have check though but remember, we’re all about eliminating possibilities here. If your iteration allows it you can actually do the same thing with the Spline’s spans (parts between adjacent control points). At this point if your Spline has P control points you essentially saved (P-2)/(P-1)th of the work (that is, the most) not even counting points that are outside of the Spline’s reach ((e.g. if you have 6 control points which result in 5 spans and you identify the span you need to look at you saved looking at the other 4)).

By this point you might have realied that it’s possible to do a binary search on the Spline (or only  on 1 span) for the X coordinate. Once you found the Spline’s point that has the same X coordinate as your random point you check the Y as well for the final verdict. And that actually only takes O(log(S)) time which is a very significant improvement. Your code might look something like this:

var spline, delta;

binaryFindByX (possibleIntersection, firstX, lastX) {
    middleX = firstX + (lastX - firstX) / 2;
    middlePoint = spline.pointAt(middleX);

    if (Math.abs(possibleIntersection.x - middlePoint.x) <= delta)
        return possibleIntersection.dst(middlePoint) <= delta ? possibleIntersection : null;
    else if (possibleIntersection.x < middlePoint.x)
        return binaryFindByX(possibleIntersection, firstX, middleX);
    else
        return binaryFindByX(possibleIntersection, middleX, lastX);
 }

binaryFindByX(pointOfLine, spline.getFirstX, spline.getLastX)

That said you still have to iterate through the Line’s points but do note that I was trying to shorten the processing of the Spline. In my case a Spline was longer and by definition more complex than the Line so it made more sense, but you can very much apply this logic the other way around.

The result is O(L*log(S)) complexity. That is a great improvement even by itself but in practice when we apply these modifications on the more complex object this really makes a huge difference in performance.

implementation

The XFlatSpline implementation (alongside with other Catmull-Rom utilities) is available on GitHub. The ‘calculateIntersection’ function will yield all intersections and uses ‘getPointOnSpline’ which implements the binary search based on the X coordinate. There’s a desktop demo where you can try it for yourself.

Leave a Reply

Your email address will not be published. Required fields are marked *