This demo illustrates the classic Graphic Gems algorithm for
computing the closest point on a cubic Bezier curve to an arbitrary
point. The original Gem code was hardcoded for cubic curves. The
Actionscript 3 implemenation in Singularity works for either quadratic
or cubic Bezier's.
At the heart of the method is a root finder that uses geometric
properties of Beziers to find roots of a polynomial in Bezier form. The
algorithm computes the innter product of B(t)P and B'(t) and then
converts this to fifthorder Bezier form. The Bezier root finder returns
roots (crossings of the horizontal axis with uniform parameterization).
The distance to each candidate solution is compared to the distance
from the specified point to the endpoints of the curve to compute the
tparameter at minimum distance from the point.
The port of the original C code is not exact; the signature of
several methods was changed and the code will eventually be moved away
from reliance on twodimensional arrays. It will be optimized for 1D
array access. The closest point code resides in the new BezierUtils
class.
There are some issues with this algorithm, including cusps and
alternate optimia. These and alternate approaches to the problem will be
discussed in the future.
This example requires the Flash™ 9 player.
