Ohhh. You want to get the offset-curves of an bezier curve.
Bad news. this is hard because these curves can't be simply derived numerical. They contain all kinds of intersections, loops and other nasty stuff.
There are some approximations though. The best approach I've read so far is from a paper by Thomas F. Hain (Fast, Precise Flattening of Cubic Bézier Path and Offset Curves).
He does flattening, so his paper is mostly about decomposes the offset curves into line-segments and circular arc-segments, but you can merge them back to beziers later.
For better understanding you may want to read his other bezier related papers as well.
There's some simple math behind calculating the positions, you can read about it in every paper discussing Bézier curves, even on wikipedia. Anyway, I can relate to everybody who's in trouble to actually implement it in code, so I wrote this sample UIView as it's probably the easiest way to get you started.
#import "MBBezierView.h"
CGFloat bezierInterpolation(CGFloat t, CGFloat a, CGFloat b, CGFloat c, CGFloat d) {
CGFloat t2 = t * t;
CGFloat t3 = t2 * t;
return a + (-a * 3 + t * (3 * a - a * t)) * t
+ (3 * b + t * (-6 * b + b * 3 * t)) * t
+ (c * 3 - c * 3 * t) * t2
+ d * t3;
}
@implementation MBBezierView
- (void)drawRect:(CGRect)rect {
CGPoint p1, p2, p3, p4;
p1 = CGPointMake(30, rect.size.height * 0.33);
p2 = CGPointMake(CGRectGetMidX(rect), CGRectGetMinY(rect));
p3 = CGPointMake(CGRectGetMidX(rect), CGRectGetMaxY(rect));
p4 = CGPointMake(-30 + CGRectGetMaxX(rect), rect.size.height * 0.66);
[[UIColor blackColor] set];
[[UIBezierPath bezierPathWithRect:rect] fill];
[[UIColor redColor] setStroke];
UIBezierPath *bezierPath = [[[UIBezierPath alloc] init] autorelease];
[bezierPath moveToPoint:p1];
[bezierPath addCurveToPoint:p4 controlPoint1:p2 controlPoint2:p3];
[bezierPath stroke];
[[UIColor brownColor] setStroke];
for (CGFloat t = 0.0; t <= 1.00001; t += 0.05) {
CGPoint point = CGPointMake(bezierInterpolation(t, p1.x, p2.x, p3.x, p4.x), bezierInterpolation(t, p1.y, p2.y, p3.y, p4.y));
UIBezierPath *pointPath = [UIBezierPath bezierPathWithArcCenter:point radius:5 startAngle:0 endAngle:2*M_PI clockwise:YES];
[pointPath stroke];
}
}
@end
This is what I get:
Best Answer
I've written some quick-and-dirty code that estimates this for Bézier curves of any degree. (Note: this is pseudo-brute force, not a closed-form solution.)
Demo: http://phrogz.net/svg/closest-point-on-bezier.html
The code above uses the vmath library to efficiently lerp between vectors (in 2D, 3D, or 4D), but it would be trivial to replace the
lerp()
call inbézierPoint()
with your own code.Tuning the Algorithm
The
closestPoint()
function works in two phases:localMinimum()
function to hunt the region around the smallest distance, using a binary search to find the t and point that produces the true smallest distance.The value of
scans
inclosestPoint()
determines how many samples to use in the first pass. Fewer scans is faster, but increases the chances of missing the true minimum point.The
ε
limit passed to thelocalMinimum()
function controls how long it continues to hunt for the best value. A value of1e-2
quantizes the curve into ~100 points, and thus you can see the points returned fromclosestPoint()
popping along the line. Each additional decimal point of precision—1e-3
,1e-4
, …—costs about 6-8 additional calls tobézierPoint()
.