Closest Point on Bezier Preview

For teaching purposes, multiple solutions to this problem will be presented. The textbook approach goes something like this; given a Bezier curve B(t) and a point P, the closest point to P on the curve satisfies the condition that the inner product of B(t)-P and B'(t) is zero (or the line segment from P to the closest point on the Bezier is perpendicular to the tangent at that point). An astute reader may wonder about singularities such as cusps where no unique tangent exists at a point that also happens to the be the closest point on the curve to P.

This method is most commonly applied to quads and cubics. In the case of a cubic, B(t) is a third-degree polynomial and B'(t) is a second-degree polynomial. Solving for the appropriate parameter values involves finding the roots of a fifth-degree polynomial. It’s not just a simple case of ‘use Newton’s method (or any other method)’ as there could be more than one root.

The case for a quadratic Bezier is a bit simpler as it requires roots of only a third-degree polynomial. The case is further simplified by the fact that we seek roots on a known interval, i.e. [0,1], so it’s not the same as asking for all roots of a general polynomial. For the third-degree case, any single root-finder may be used to find a single root in [0.1]. A simple approach is to use bisection to quickly locate a candidate sub-interval (in which there is a sign change), then apply the root finder (Jack Crenshaw’s TWBRF has been implemented in Singularity and it does not require an initial guess). Once a single root is found, synthetic division is used to factor out that root, leaving a second-degree polynomial. The venerable quadratic formula can be used at that point.

Once a list of candidate roots is generated, the t-values are used to generate the x-y coordinates and the actual distances to the point P are compared to the distances from P to the endpoints of the Bezier curve. The closest point of all these candidates is selected as the closest point on the Bezier to the specified point.

As it happens, this has already been implemented in the cubic Bezier class for the general y-at-x method. Extracting the algorithm as a general utility for a cubic polynomial root-finder is pretty easy. Extending the approach to work for higher-degree polynomials such as fifth-degree is also straightforward. Although this approach is tractable for the problem at hand, it is not recommended as a general-purpose root-finder for arbitrary-degree polynomials.

There is an alternate approach (discussed in Graphic Gems) which converts the fifth-degree curve to Bezier form and exploits specific properties of Bezier curves to find the roots.  This Gem has been published in C and converted to Java (I suppose that means it’s time for an Actionscript version).

Bezier splines can be handled with this approach by using an extension of Bezier clipping to disqualify segments of the composite curve that can not contain the closest point. Each remaining segment of the spline is a single cubic Bezier and the above algorithm is applied recursively.

In addition to singularities, it may be the case that multiple points exist that are all the same minimum distance from the Bezier curve. First, we will look at the standard approaches and use some of these cases to introduce alternate methods to solve the problem.

Just a sneak preview of what’s ahead.