Download the commented source code.
There are multiple ways to project a point onto a Bézier curve. If you do the math analytically, you are often left with some high order polynomial that you must solve with a root finding algorithm. An easier way is to use a minimisation algorithm to find the smallest distance between a point and the curve.
In my previous post I created a custom cubic Bézier class to help with finding the position and angle of points along a curve. Here we will extend that class to include a method for projecting a given point onto the curve. We will use the Golden Section Search to perform the required minimisation (see this post about the implementation details). We will be referencing code from those two posts so you might want to read them before continuing.
We are trying to find the location of the smallest distance between a given point and the curve - not the distance itself. We could base the minimisation algorithm on the distance between two points, however, the same result is achieved if we minimise the distance squared between two points. Using the distance squared eliminates the need to perform the expensive square root function over and over. Let's create an inline function for efficiency and convenience.
NS_INLINE CGFloat CGPointDistanceSquared(CGPoint leftPoint, CGPoint rightPoint)
{
return (leftPoint.x-rightPoint.x)*(leftPoint.x-rightPoint.x) + (leftPoint.y-rightPoint.y)*(leftPoint.y-rightPoint.y);
}Now let's find the Bézier parameter t that minimises the distance squared between a given point and the curve.
- (CGFloat)projectedTValueClosestToPoint:(CGPoint)pointToProject goldenSectionUnimodalSearchSamples:(NSUInteger)unimodalSearchSamples tau:(CGFloat)tau {
CGFloat projectedT = [PWAlgorithm goldenSectionSearchWithFunction1D:^CGFloat(CGFloat x) {
return CGPointDistanceSquared([self outputAtT:x], pointToProject);
} unimodalSearchLowerX:0.0 unimodalSearchUpperX:1.0 unimodalSearchSamples:unimodalSearchSamples tau:tau];
// check the extremidies
CGPoint projectedPoint = [self outputAtT:projectedT];
CGFloat distanceSquaredToProjectedPoint = CGPointDistanceSquared(projectedPoint, pointToProject);
if(CGPointDistanceSquared(pointToProject, [self outputAtT:0.0]) <= distanceSquaredToProjectedPoint) {
return 0.0;
}
if(CGPointDistanceSquared(pointToProject, [self outputAtT:1.0]) <= distanceSquaredToProjectedPoint) {
return 1.0;
}
return projectedT;
}We create a NSBlock to pass as an argument to our Golden Section Search. The block takes a single parameter that represents t, and returns the distance squared between the provided point and the curve at that t value. We know that t must remain between 0 and 1, so we use that as the bounds for the unimodal search space. The number of unimodal search samples should approximately align with the bendiness of the curve - a straight line doesn't need a unimodal search (0 samples) where as a bendy line will need a few.
The Golden Section Search does most of the hard work. The projected t returned should be very close to correct answer, as long as the Golden Section parameters have been set correctly.
Occasionally the smallest distance from the point to the curve will occur at one of the endpoints. The result returned from the search will be fairly close to the endpoint, but sometimes not exactly at the endpoint, as the Golden Section Search assumes the search space is unimodal. To increase accuracy, we can check if the distance between the point and each endpoint is smaller than the result found in the search. If so, we can just return 0 or 1, representing the particular endpoint.
Sometimes you don't really care what the projected t value is, you only care about the projected point itself. Let's create another convenience function that returns the projected point instead of the project t value.
- (CGPoint)projectedPointClosestToPoint:(CGPoint)pointToProject goldenSectionUnimodalSearchSamples:(NSUInteger)unimodalSearchSamples tau:(CGFloat)tau {
CGFloat projectedT = [self projectedTValueClosestToPoint:pointToProject goldenSectionUnimodalSearchSamples:unimodalSearchSamples tau:tau
];
return [self outputAtT:projectedT];
}Now we can project points onto Bézier curves quickly and accurately! The same method can be used to project a point onto a sequence of Bézier curves.
Here's a demo of the code in action.
