Flattening a CGPath

Question

Simply put, I'm looking for an equivalent to NSBezierPath's -bezierPathByFlatteningPath that can be used on iOS. It doesn't matter to me whether this is a function dealing directly with a CGPath or a method on UIBezierPath, because the two can easily be converted back and forth. Neither the CGPath Reference nor the UIBezierPath Class Reference indicate the presence of any such function or method.

Also: I'm aware of CGPath's CGPathApply function, and I lack both the time and the skill-set to implement my own flattening algorithm by iterating over the path's elements in a CGPathApplierFunction. I'm looking for an existing solution to this—an applier function, a category on UIBezierPath, etc. Surely one exists.

Answer 1

Erica Sadun provides a set of useful functions to deal with UIBezierPath and CGPathRef.

This code is used in this book.

She does not provide an implementation of a CGPathRef flattening, but it can be easily done using functions that can be found here: https://github.com/erica/iOS-Drawing/blob/master/C05/Quartz%20Book%20Pack/Bezier/BezierFunctions.m

Particulary, these functions will help discretize the non linear Bezier segments:

float CubicBezier(float t, float start, float c1, float c2, float end)
float QuadBezier(float t, float start, float c1, float end)
CGPoint CubicBezierPoint(CGFloat t, CGPoint start, CGPoint c1, CGPoint c2, CGPoint end);
CGPoint QuadBezierPoint(CGFloat t, CGPoint start, CGPoint c1, CGPoint end);

So basically, initialize an empty CGMutablePathRef, and for each CGPath element in the original path, either copy it if it's linear, or discretize it according to the degree of the Bezier segment.

You may also want to apply the Ramer–Douglas–Peucker algorithm to remove unnecessary points.

You could also directly use: - (NSArray *) interpolatedPathPoints which returns an NSArray of points which can be used to build an approximation of the path. The algorithm is naive, so you have to simplify the result in the case, e.g , where a cubic Bezier path would be linear (if the control points are aligned); just as before, Ramer–Douglas–Peucker algorithm does the job.

Here is what the actual discretization looks like. Code is not self contained, you'll have to use all dependencies.

- (NSArray *) interpolatedPathPoints
{
    NSMutableArray *points = [NSMutableArray array];
    BezierElement *current = nil;
    int overkill = 3;
    for (BezierElement *element in self.elements)
    {
        switch (element.elementType)
        {
            case kCGPathElementMoveToPoint:
            case kCGPathElementAddLineToPoint:
                [points addObject:[NSValue valueWithCGPoint:element.point]];
                current = element;
                break;
            case kCGPathElementCloseSubpath:
                current = nil;
                break;
            case kCGPathElementAddCurveToPoint:
            {
                for (int i = 1; i < NUMBER_OF_BEZIER_SAMPLES * overkill; i++)
                {
                    CGFloat percent = (CGFloat) i / (CGFloat) (NUMBER_OF_BEZIER_SAMPLES * overkill);
                    CGPoint p = CubicBezierPoint(percent, current.point, element.controlPoint1, element.controlPoint2, element.point);
                    [points addObject:[NSValue valueWithCGPoint:p]];
                }
                [points addObject:[NSValue valueWithCGPoint:element.point]];
                current = element;
                break;
            }
            case kCGPathElementAddQuadCurveToPoint:
            {
                for (int i = 1; i < NUMBER_OF_BEZIER_SAMPLES * overkill; i++)
                {
                    CGFloat percent = (CGFloat) i / (CGFloat) (NUMBER_OF_BEZIER_SAMPLES * overkill);
                    CGPoint p = QuadBezierPoint(percent, current.point, element.controlPoint1, element.point);
                    [points addObject:[NSValue valueWithCGPoint:p]];
                }
                [points addObject:[NSValue valueWithCGPoint:element.point]];
                current = element;
                break;
            }
        }
    }
    return points;
}

Code belongs to Erica Sadun. See here for the complete implementation: https://github.com/erica/iOS-Drawing

Rob Napier also wrote about Bezier curves in iOS 6 Pushing the limits, Chapter 26 Fancy Text Layout. He was not trying to flatten a full UIBezierPath, only one cubic Bezier path defined with four points, but really that's exactly the same thing (discretizing a Bezier path) Also, you may find this article interesting: http://robnapier.net/faster-bezier