寻找CGPath的中心

Question

寻找CGPath的中心

10

我有一个任意的CGPath，我想找到它的地理中心。我可以使用CGPathGetPathBoundingBox获取路径边界框，并找到该框的中心。但是有没有更好的方法来找到路径的中心？

更新：对于那些喜欢看代码的人：这里是使用Adam在答案中建议的点平均值方法的代码（不要错过下面答案中更好的技术）...

    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));

如果您有更好的想法，请分享！

- EFC

6个回答

6

对于我所处理的一些多边形来说，简单的路径点平均值并不足够。

我使用了面积来实现它（参见维基百科，多边形重心和Paul Bourke的页面）。这可能不是最有效的实现，但对我来说很有效。

请注意，它仅适用于封闭的、非相交的多边形。顶点假定按照沿多边形周长出现的顺序编号，并且最后一个点假定与第一个点相同。

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);
}

- masam

我复制并粘贴了这段代码，但似乎返回的质心是错误的。 - etayluz

@etayluz，你能具体说明一下吗？你确定你使用的是封闭多边形吗？此外，请注意上面的代码不是CGPath中所有点的简单平均值，正如我在答案中指出的那样。 - masam

这里有一个 bug，kCGPathElementAddCurveToPoint 只有 3 个点，而不是 4 个。 - yonilevy

谢谢@yonilevy-确实是个笔误。 - masam

2

这段文字的翻译如下：

所有路径点的x和y的简单平均值是否给出了您想要的点？计算x和y的一个值。我画了一个快速草图，这种方法给出了一个可信的答案。

请参见维基百科，有限点集的质心。

如果不是，则可能需要先找到该区域的面积 - 请参见 Paul Bourke的页面。

- Adam Eberbach

非常好！获取平均点比边界中心要好得多，而且很容易实现。谢谢！ - EFC

1

我更新了Adam的答案，使其适用于Swift4版本：

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))
    }
}

但是要注意，CGPath可能有额外的移动命令，这会因为点的数量而破坏这个逻辑。

- Kirow

-1

这里是质心，来拿吧：

-(CLLocationCoordinate2D)getCentroidFor:(GMSMutablePath *)rect
{
  CLLocationCoordinate2D coord = [rect coordinateAtIndex:0];
  double minX = coord.longitude;
  double maxX = coord.longitude;
  double minY = coord.latitude;
  double maxY = coord.latitude;
  for (int i = 1; i < rect.count; i++)
  {
    CLLocationCoordinate2D coord = [rect coordinateAtIndex:i];
    if (minX > coord.longitude)
      minX = coord.longitude;
    if (maxX < coord.longitude)
      maxX = coord.longitude;
    if (minY > coord.latitude)
      minY = coord.latitude;
    if (maxY < coord.latitude)
      maxY = coord.latitude;
  }

  CLLocationDegrees centerX = minX + ((maxX - minX) / 2);
  CLLocationDegrees centerY = minY + ((maxY - minY) / 2); 
    return CLLocationCoordinate2DMake(centerY, centerX);
}

- etayluz

请再次阅读原帖的问题。这个回答与问题无关且没有用处。 - Womble

Swift 4 版本？谢谢。 - famfamfam

-3

寻找CGPath的边界框并取其中心。

CGRect boundingBox = CGPathGetBoundingBox(my_path); my_center_point = ccp(boundingBox.origin.x+boundingBox.size.width/2, boundingBox.origin.y+boundingBox.size.height/2);

- jjpp

正如我在问题陈述中所说的，寻找边界框的中心在这种情况下不是一个好的解决方案。 - EFC

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam · Accepted Answer

该技术是有效的，但你在问题中提供的代码不行。据我所知，那只适用于仅涉及直线多边形的少数情况，且你必须有一个点列表，且尚未创建CGPath对象。

我需要对任意CGPath对象执行此操作。使用Adam（另一个Adam）的建议和Apple的CGPathApply，我得出了这个非常好的解决方案：

{
            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;
}