how to make a parallel bezier curve heuristically

Question

I have only found this blog with a relevant answer http://seant23.wordpress.com/2010/11/12/offset-bezier-curves/ ,but unfortunately i don't know the language and can't understand the maths behind it. What i need is to know how to make a bezier curve parallel to the one that i have.

I have a Point, Segment and Path class, but i don't understand how to divide the path into segments. The Point class has the CGPoint location public variable, the Segment class has as properties 4 points, Point *control1, *control2, *point2 and*point1; the Path class contains an NSMutableArray of segments and a Point startPoint.

I am new to objective c and i would really appreciate some help, if not for my specific class construction, at least for a more general method.

Answer 1

I don't know about the specific problem you're solving, but one cute (and very easy) solution is to just render the outline outline of a bezier curve, e.g.:

This is easily done using Core Graphics (in this case, a drawRect of a UIView subclass):

- (void)drawRect:(CGRect)rect {
    CGPathRef path = [self newBezierPath];
    CGPathRef outlinePath = CGPathCreateCopyByStrokingPath(path, NULL, 10, kCGLineCapButt, kCGLineJoinBevel, 0);

    CGContextRef context = UIGraphicsGetCurrentContext();
    CGContextSetLineWidth(context, 3.0);
    CGContextAddPath(context, outlinePath);
    CGContextSetStrokeColorWithColor(context, [[UIColor redColor] CGColor]);
    CGContextDrawPath(context, kCGPathStroke);

    CGPathRelease(path);
    CGPathRelease(outlinePath);
}

- (CGPathRef)newBezierPath {
    CGPoint point1 = CGPointMake(10.0, 50.0);
    CGPoint point2 = CGPointMake(self.bounds.size.width - 10.0, point1.y + 150.0);

    CGPoint controlPoint1 = CGPointMake(point1.x + 400.0, point1.y);
    CGPoint controlPoint2 = CGPointMake(point2.x - 400.0, point2.y);

    CGMutablePathRef path = CGPathCreateMutable();
    CGPathMoveToPoint(path, NULL, point1.x, point1.y);
    CGPathAddCurveToPoint(path, NULL, controlPoint1.x, controlPoint1.y, controlPoint2.x, controlPoint2.y, point2.x, point2.y);

    return path;
}

Or in Swift 3:

override func draw(_ rect: CGRect) {
    let path = bezierPath().cgPath
    let outlinePath = path.copy(strokingWithWidth: 10, lineCap: .butt, lineJoin: .bevel, miterLimit: 0)

    let context = UIGraphicsGetCurrentContext()!
    context.setLineWidth(3)
    context.addPath(outlinePath)
    context.setStrokeColor(UIColor.red.cgColor)
    context.strokePath()
}

private func bezierPath() -> UIBezierPath {
    let point1 = CGPoint(x: 10.0, y: 50.0)
    let point2 = CGPoint(x: bounds.size.width - 10.0, y: point1.y + 150.0)

    let controlPoint1 = CGPoint(x: point1.x + 400.0, y: point1.y)
    let controlPoint2 = CGPoint(x: point2.x - 400.0, y: point2.y)

    let path = UIBezierPath()
    path.move(to: point1)
    path.addCurve(to: point2, controlPoint1: controlPoint1, controlPoint2: controlPoint2)

    return path
}

If you really want to draw a parallel path, that's more complicated. But you can render something like this (original bezier path in red, a "parallel" line in blue).

I'm not entirely sure about the algorithm you've identified, but I rendered this by

• calculating the bezier points (the red path) myself, breaking it up finely enough to make the effect smooth;
• calculate the angle between each point and the next;
• calculate the coordinates of the offset path (the blue one) by taking the points on the bezier path, and calculating new points that are perpendicular to the angle I just determined; and
• using those offset point coordinates, draw a new series of line segments to render the parallel line to the bezier.

Thus, in Objective-C, that might look like:

- (void)drawRect:(CGRect)rect {
    CGPoint point1 = CGPointMake(10.0, 50.0);
    CGPoint point2 = CGPointMake(self.bounds.size.width - 10.0, point1.y + 150.0);

    CGPoint controlPoint1 = CGPointMake(point1.x + 400.0, point1.y);
    CGPoint controlPoint2 = CGPointMake(point2.x - 400.0, point2.y);

    // draw original bezier path in red

    [[UIColor redColor] setStroke];

    [[self bezierPathFromPoint1:point1
                         point2:point2
                  controlPoint1:controlPoint1
                  controlPoint2:controlPoint2] stroke];

    // calculate and draw offset bezier curve in blue

    [[UIColor blueColor] setStroke];

    [[self offsetBezierPathBy:10.0
                       point1:point1
                       point2:point2
                controlPoint1:controlPoint1
                controlPoint2:controlPoint2] stroke];
}

- (UIBezierPath *)bezierPathFromPoint1:(CGPoint)point1
                                point2:(CGPoint)point2
                         controlPoint1:(CGPoint)controlPoint1
                         controlPoint2:(CGPoint)controlPoint2 {
    UIBezierPath *path = [UIBezierPath bezierPath];

    [path moveToPoint:point1];
    [path addCurveToPoint:point2 controlPoint1:controlPoint1 controlPoint2:controlPoint2];

    return path;
}

- (UIBezierPath *)offsetBezierPathBy:(CGFloat)offset
                              point1:(CGPoint)point1
                              point2:(CGPoint)point2
                       controlPoint1:(CGPoint)controlPoint1
                       controlPoint2:(CGPoint)controlPoint2 {
    UIBezierPath *path = [UIBezierPath bezierPath];
    static NSInteger numberOfPoints = 100;

    CGPoint previousPoint = [self cubicBezierAtTime:0.0
                                             point1:point1
                                             point2:point2
                                      controlPoint1:controlPoint1
                                      controlPoint2:controlPoint2];
    CGPoint point;
    double angle;

    for (NSInteger i = 1; i <= numberOfPoints; i++) {
        double t = (double) i / numberOfPoints;

        point = [self cubicBezierAtTime:t
                                 point1:point1
                                 point2:point2
                          controlPoint1:controlPoint1
                          controlPoint2:controlPoint2];

        // calculate the angle to the offset point
        // this is the angle between the two points, plus 90 degrees (pi / 2.0)

        angle = atan2(point.y - previousPoint.y, point.x - previousPoint.x) + M_PI_2;


        if (i == 1)
            [path moveToPoint:[self offsetPoint:previousPoint by:offset angle:angle]];

        previousPoint = point;
        [path addLineToPoint:[self offsetPoint:previousPoint by:offset angle:angle]];
    }

    return path;
}

// return point offset by particular distance and particular angle

- (CGPoint)offsetPoint:(CGPoint)point by:(CGFloat)offset angle:(double)angle {
    return CGPointMake(point.x + cos(angle) * offset, point.y + sin(angle) * offset);
}

// Manually calculate cubic bezier curve
//
// B(t) = (1-t)^3 * point1 + 3 * (1-t)^2 * t controlPoint1 + 3 * (1-t) * t^2 * pointPoint2 + t^3 * point2

- (CGPoint)cubicBezierAtTime:(double)t
                      point1:(CGPoint)point1
                      point2:(CGPoint)point2
               controlPoint1:(CGPoint)controlPoint1
               controlPoint2:(CGPoint)controlPoint2 {
    double oneMinusT = 1.0 - t;
    double oneMinusTSquared = oneMinusT * oneMinusT;
    double oneMinusTCubed = oneMinusTSquared * oneMinusT;

    double tSquared = t * t;
    double tCubed = tSquared * t;

    CGFloat x = point1.x * oneMinusTCubed +
    3.0 * oneMinusTSquared * t * controlPoint1.x +
    3.0 * oneMinusT * tSquared * controlPoint2.x +
    tCubed * point2.x;
    CGFloat y = point1.y * oneMinusTCubed +
    3.0 * oneMinusTSquared * t * controlPoint1.y +
    3.0 * oneMinusT * tSquared * controlPoint2.y +
    tCubed * point2.y;

    return CGPointMake(x, y);
}

Or, in Swift 3:

override func draw(_ rect: CGRect) {
    let point1 = CGPoint(x: 10.0, y: 50.0)
    let point2 = CGPoint(x: bounds.size.width - 10.0, y: point1.y + 150.0)

    let controlPoint1 = CGPoint(x: point1.x + 400.0, y: point1.y)
    let controlPoint2 = CGPoint(x: point2.x - 400.0, y: point2.y)

    UIColor.red.setStroke()
    bezierPath(from: point1, to: point2, withControl: controlPoint1, and: controlPoint2).stroke()

    UIColor.blue.setStroke()
    offSetBezierPath(by: 5, from: point1, to: point2, withControl: controlPoint1, and: controlPoint2).stroke()
}

private func bezierPath(from point1: CGPoint, to point2: CGPoint, withControl controlPoint1: CGPoint, and controlPoint2:CGPoint) -> UIBezierPath {
    let path = UIBezierPath()

    path.move(to: point1)
    path.addCurve(to: point2, controlPoint1: controlPoint1, controlPoint2: controlPoint2)

    return path
}

private func offSetBezierPath(by offset: CGFloat, from point1: CGPoint, to point2: CGPoint, withControl controlPoint1: CGPoint, and controlPoint2:CGPoint) -> UIBezierPath {
    let path = UIBezierPath()

    let numberOfPoints = 100

    var previousPoint = cubicBezier(at: 0, point1: point1, point2: point2, controlPoint1: controlPoint1, controlPoint2: controlPoint2)

    for i in 1 ... numberOfPoints {
        let time = CGFloat(i) / CGFloat(numberOfPoints)
        let point = cubicBezier(at: time, point1: point1, point2: point2, controlPoint1: controlPoint1, controlPoint2: controlPoint2)

        // calculate the angle to the offset point
        // this is the angle between the two points, plus 90 degrees (pi / 2.0)

        let angle = atan2(point.y - previousPoint.y, point.x - previousPoint.x) + .pi / 2;

        if i == 1 {
            path.move(to: calculateOffset(of: previousPoint, by: offset, angle: angle))
        }

        previousPoint = point
        path.addLine(to: calculateOffset(of: previousPoint, by: offset, angle: angle))
    }

    return path
}

/// Return point offset by particular distance and particular angle
///
/// - Parameters:
///   - point: Point to offset.
///   - offset: How much to offset by.
///   - angle: At what angle.
///
/// - Returns: New `CGPoint`.

private func calculateOffset(of point: CGPoint, by offset: CGFloat, angle: CGFloat) -> CGPoint {
    return CGPoint(x: point.x + cos(angle) * offset, y: point.y + sin(angle) * offset)
}

/// Manually calculate cubic bezier curve
///
/// B(t) = (1-t)^3 * point1 + 3 * (1-t)^2 * t controlPoint1 + 3 * (1-t) * t^2 * pointPoint2 + t^3 * point2
///
/// - Parameters:
///   - time:          Time, a value between zero and one.
///   - point1:        Starting point.
///   - point2:        Ending point.
///   - controlPoint1: First control point.
///   - controlPoint2: Second control point.
///
/// - Returns: Point on bezier curve.

private func cubicBezier(at time: CGFloat, point1: CGPoint, point2: CGPoint, controlPoint1: CGPoint, controlPoint2: CGPoint) -> CGPoint {
    let oneMinusT = 1.0 - time
    let oneMinusTSquared = oneMinusT * oneMinusT
    let oneMinusTCubed = oneMinusTSquared * oneMinusT

    let tSquared = time * time
    let tCubed = tSquared * time

    var x = point1.x * oneMinusTCubed
    x += 3.0 * oneMinusTSquared * time * controlPoint1.x
    x += 3.0 * oneMinusT * tSquared * controlPoint2.x
    x += tCubed * point2.x

    var y = point1.y * oneMinusTCubed
    y += 3.0 * oneMinusTSquared * time * controlPoint1.y
    y += 3.0 * oneMinusT * tSquared * controlPoint2.y
    y += tCubed * point2.y

    return CGPoint(x: x, y: y)
}

Answer 2

You might have seen the link to my article on Sean's blog, if not: http://pomax.github.io/bezierinfo/#offsetting covers offset curves in detail. It refers to some subjects covered higher up in the article, like splitting curves at inflection points, but the takehome message is:

1. you cannot create a true offset curve C for an arbitrary curve B. The article explains why, but the tl;dr is that a bezier curve is an integer polynomial, and except in a minute edge case, their offset curves can be perfectly modelled with a mathematical function, but it is not an integer polynomial, and as such isn't conveniently another Bezier curve.
2. you can flatten to curve to a "looks like a curve" polygon, and offset that just fine. This can be done really fast, and if you use enough segments, will look just fine. It just won't scale, and you have to determine how many segments to use based on the offsetting distance.
3. you can cut up the curve into small sections that can be offset without loss of precision by other curves. This is slower, but allows arbitrary distance between the curve and its offset.

If there is no prebuilt offsetting function in your codebase, then you're going to have to implement it yourself, in which case you're going to have to take a day or two out of your dev and dedicate it to understanding how this works (for which I'd pretty much recommend running through the bezier article. writing the offsetting algorithm requires having the functions it depends on available).