Find a point, a given distance, along a simple cubic bezier curve. (On an iPhone!)

Question

Imagine you have a completely normal four-point bezier curve (two points and two control points) created using curveToPoint:controlPoint1:controlPoint2: in your cocoa application. Here it is:

How do you find points, along the curve? So, starting at the StartPoint, what are the x,y coords for a point that is distance D along the curve?

To be clear, iOS does this easily, there are functions that let you trivially animate something along any such curve. (Unfortunately there is no function to spit out the numerical x,y position of each step along the way.)

If there is an incredibly simple answer to this, sorry for being so DUMB.

-- Further .....................

In fact, if you also need the code for the SLOPE at a given point, and also a more explanatory version of Michal's awesome step calculation below, go to question 4089443. Hope it helps.

Answer 1

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: