Finding the center of a CGPath

Question

I have an arbitrary CGPath and I'd like to find it's geographic center. I can get the path bounding box with CGPathGetPathBoundingBox and then find the center of that box. But is there a better way to find the center of a path?

Update for those who like to see code: here is code for using the average-of-points method suggested by Adam in the answers (don't miss the even better technique in the answers below)...

    BOOL moved = NO; // the first coord should be a move, the rest add lines
    CGPoint total = CGPointZero;
    for (NSDictionary *coord in [polygon objectForKey:@"coordinates"]) {
        CGPoint point = CGPointMake([(NSNumber *)[coord objectForKey:@"x"] floatValue], 
                                    [(NSNumber *)[coord objectForKey:@"y"] floatValue]);
        if (moved) {
            CGContextAddLineToPoint(context, point.x, point.y);
            // calculate totals of x and y to help find the center later
            // skip the first "move" point since it is repeated at the end in this data
            total.x = total.x + point.x;
            total.y = total.y + point.y;
        } else {
            CGContextMoveToPoint(context, point.x, point.y);
            moved = YES; // we only move once, then we add lines
        }
    }

    // the center is the average of the total points
    CGPoint center = CGPointMake(total.x / ([[polygon objectForKey:@"coordinates"] count]-1), total.y / ([[polygon objectForKey:@"coordinates"] count]-1));

If you have a better idea, please share!

Answer 1

Does the simple average of all x and all y for the points in the path give the point you want? Calculate one value for x and one for y. I made a quick sketch and this method gave a believable answer.

See wikipedia, finding the centroid of a finite set of points.

If not you may need to first find the area - see Paul Bourke's page.

Answer 2

For me, the simple average of all points in the path did not suffice for some of the polygons I was dealing with.

I implemented it using the area (see wikipedia, Centroid of polygon and Paul Bourke's page). It might not be the most efficient implementation but it works for me.

Note that it only works for closed, non-intersecting polygons. The vertices are assumed to be numbered in order of their occurrence along the polygon's perimeter, and the last point is assumed to be the same as the first point.

CGPoint GetCenterPointOfCGPath (CGPathRef aPath)
{
    // Convert path to an array
    NSMutableArray* a = [NSMutableArray new];
    CGPathApply(aPath, (__bridge void *)(a), convertToListOfPoints);
    return centroid(a);
}

static void convertToListOfPoints(void* info, const CGPathElement* element)
{
    NSMutableArray* a = (__bridge NSMutableArray*) info;

    switch (element->type)
    {
        case kCGPathElementMoveToPoint:
        {
            [a addObject:[NSValue valueWithCGPoint:element->points[0]]];
        }
        break;
        case kCGPathElementAddLineToPoint:
        {
            [a addObject:[NSValue valueWithCGPoint:element->points[0]]];
        }
        break;
        case kCGPathElementAddQuadCurveToPoint:
        {
            for (int i=0; i<2; i++)
                [a addObject:[NSValue valueWithCGPoint:element->points[i]]];
        }
        break;
        case kCGPathElementAddCurveToPoint:
        {
            for (int i=0; i<3; i++)
                [a addObject:[NSValue valueWithCGPoint:element->points[i]]];
        }
        break;
        case kCGPathElementCloseSubpath:
        break;
    }
}

double polygonArea(NSMutableArray* points) {
    int i,j;
    double area = 0;
    int N = [points count];

    for (i=0;i<N;i++) {
        j = (i + 1) % N;
        CGPoint pi =  [(NSValue*)[points objectAtIndex:i] CGPointValue];
        CGPoint pj =  [(NSValue*)[points objectAtIndex:j] CGPointValue];
        area += pi.x * pj.y;
        area -= pi.y * pj.x;
    }

    area /= 2;
    return area;
}

CGPoint centroid(NSMutableArray* points) {
    double cx = 0, cy = 0;
    double area = polygonArea(points);

    int i, j, n = [points count];

    double factor = 0;
    for (i = 0; i < n; i++) {
        j = (i + 1) % n;
        CGPoint pi =  [(NSValue*)[points objectAtIndex:i] CGPointValue];
        CGPoint pj =  [(NSValue*)[points objectAtIndex:j] CGPointValue];
        factor = (pi.x * pj.y - pj.x * pi.y);
        cx += (pi.x + pj.x) * factor;
        cy += (pi.y + pj.y) * factor;
    }

    cx *= 1 / (6.0f * area);
    cy *= 1 / (6.0f * area);

    return CGPointMake(cx, cy);
}

Answer 3

The technique works, but the code you put in the question doesn't. AFAICS, that only works for the few situations where you are doing straight-line polygons ONLY, and you have a list of points, and you haven't made the CGPath object yet.

I needed to do it for arbitrary CGPath objects. Using Adam's (other Adam) suggestion, and Apple's CGPathApply, I came up with this, which works very well:

{
            float dataArray[3] = { 0, 0, 0 };
            CGPathApply( (CGPathRef) YOUR_PATH, dataArray, pathApplierSumCoordinatesOfAllPoints);

            float averageX = dataArray[0] / dataArray[2];
            float averageY = dataArray[1]  / dataArray[2];
            CGPoint centerOfPath = CGPointMake(averageX, averageY);
}

static void pathApplierSumCoordinatesOfAllPoints(void* info, const CGPathElement* element)
{
    float* dataArray = (float*) info;
    float xTotal = dataArray[0];
    float yTotal = dataArray[1];
    float numPoints = dataArray[2];


    switch (element->type)
    {
        case kCGPathElementMoveToPoint:
        {
            /** for a move to, add the single target point only */

            CGPoint p = element->points[0];
            xTotal += p.x;
            yTotal += p.y;
            numPoints += 1.0;

        }
            break;
        case kCGPathElementAddLineToPoint:
        {
            /** for a line to, add the single target point only */

            CGPoint p = element->points[0];
            xTotal += p.x;
            yTotal += p.y;
            numPoints += 1.0;

        }
            break;
        case kCGPathElementAddQuadCurveToPoint:
            for( int i=0; i<2; i++ ) // note: quad has TWO not THREE
            {
                /** for a curve, we add all ppints, including the control poitns */
                CGPoint p = element->points[i];
                xTotal += p.x;
                yTotal += p.y;
                numPoints += 1.0;
            }
            break;
        case kCGPathElementAddCurveToPoint:         
            for( int i=0; i<3; i++ ) // note: cubic has THREE not TWO
            {
                /** for a curve, we add all ppints, including the control poitns */
                CGPoint p = element->points[i];
                xTotal += p.x;
                yTotal += p.y;
                numPoints += 1.0;
            }
            break;
        case kCGPathElementCloseSubpath:
            /** for a close path, do nothing */
            break;
    }

    //NSLog(@"new x=%2.2f, new y=%2.2f, new num=%2.2f", xTotal, yTotal, numPoints);
    dataArray[0] = xTotal;
    dataArray[1] = yTotal;
    dataArray[2] = numPoints;
}

Answer 4

Updated Adam's answer to swift4 version:

extension CGPath {
    func findCenter() -> CGPoint {
        class Context {
            var sumX: CGFloat = 0
            var sumY: CGFloat = 0
            var points = 0
        }

        var context = Context()

        apply(info: &context) { (context, element) in
            guard let context = context?.assumingMemoryBound(to: Context.self).pointee else {
                return
            }
            switch element.pointee.type {
            case .moveToPoint, .addLineToPoint:
                let point = element.pointee.points[0]
                context.sumX += point.x
                context.sumY += point.y
                context.points += 1
            case .addQuadCurveToPoint:
                let controlPoint = element.pointee.points[0]
                let point = element.pointee.points[1]
                context.sumX += point.x + controlPoint.x
                context.sumY += point.y + controlPoint.y
                context.points += 2
            case .addCurveToPoint:
                let controlPoint1 = element.pointee.points[0]
                let controlPoint2 = element.pointee.points[1]
                let point = element.pointee.points[2]
                context.sumX += point.x + controlPoint1.x + controlPoint2.x
                context.sumY += point.y + controlPoint1.y + controlPoint2.y
                context.points += 3
            case .closeSubpath:
                break
            }
        }

        return CGPoint(x: context.sumX / CGFloat(context.points),
                y: context.sumY / CGFloat(context.points))
    }
}

But be careful, CGPath may have extra move commands that will break this logic because of point count