iOS - 如何用无序的CGPoints绘制特定的CGPath

Question

考虑这个ASCII图：

A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ D
 |                               |
 |                               |
 |                               |
 |                               |
 |                               |
 |                               |
 |                               |
 |                               |
 |                               |
 |                               |
 |                               |
 |                               |
 |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
B                                 C

已知点A、B、C和D是NSMutableArray中的CGPoints，并已使用它们创建了一个填充的CGPath。现在考虑以下绘图：

A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ D
 |                               |
 |                               |
 |                               |
 |                               |
 |            H _ _ _ I          |
 |             |     |           |
 |             |     |           |
 |      F _ _ _|     |           |
 |       |      G    |           |
 |       |           |_ _ _ K    |
 |       |          J      |     |
 |       |                 |     |
 |_ _ _ _| _ _ _ _ _ _ _ _ |_ _ _|
B         E               L       C

CGPoints E、F、G、H、I、J、K和L已知，并已附加到NSMutableArray的末尾。

问题

如何重新排列数组中的所有点以创建类似下图所示的CGPath？

A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ D
 |                               |
 |                               |
 |                               |
 |                               |
 |            H _ _ _ I          |
 |             |     |           |
 |             |     |           |
 |      F _ _ _|     |           |
 |       |      G    |           |
 |       |           |_ _ _ K    |
 |       |          J      |     |
 |       |                 |     |
 |_ _ _ _|                 |_ _ _|
B         E               L       C

目前为止，只要我知道CGPoints的顺序，我没有任何问题来创建一个CGPath，只需通过循环它们：

CGPoint firstPoint = [[points objectAtIndex:0] CGPointValue];
CGMutablePathRef path = CGPathCreateMutable();
CGPathMoveToPoint(path, NULL, firstPoint.x, firstPoint.y);
for (int i = 0; i < [points count]; i++)
{
    CGPathAddLineToPoint(path, NULL, [[points objectAtIndex:i] CGPointValue].x, [[points objectAtIndex:i] CGPointValue].y);
}
CGPathCloseSubpath(path);

但这假设从数组i中的每个点到其后面的点i + 1都应该画一条线。在上面的图中，必须从A → B，B → E，E → F ... K → L，L → C，C → D画出线条。如果E不在B之后，C不在L之后（它们不会是），那么这显然不会正确绘制。

更多信息

1. 所有的线都相互垂直，所以所有的CGPoints都应该与前后的CGPoint共享一个x或y坐标。
2. (1的扩展)一个点将始终与它之前和之后的点成直角。
3. 无法预测点将出现在正方形的哪个位置，并且新的点集可能会按任意顺序附加到数组的末尾。
4. ...

其他可能的布局

A _ _ _ _ _ _ _ K         P _ _ _ D
 |             |           |     | 
 |             |           |     |
 |             |    N _ _ _|     |
 |             |     |      O    |
 |             |_ _ _|           |
 |            L       M          |
 |                               |
 |            F _ _ _ G          |
 |             |     |           |
 |             |     |_ _ _ I    |
 |             |    H      |     |
 |             |           |     |
 |_ _ _ _ _ _ _|           |_ _ _|
B               E         J       C


A _ _ _ _ _ _ _ _ _ _ M
 |                   |           
 |                   |           
 |                   |_ _ _ _ _ _ O
 |                  N            |
 |            H _ _ _ I          |
 |             |     |           |
 |             |     |           |
 |      F _ _ _|     |           |
 |       |      G    |           |
 |       |           |_ _ _ K    |
 |       |          J      |     |
 |       |                 |     |
 |_ _ _ _|                 |_ _ _|
B         E               L       C

- lobianco

---

你是如何将这些点放入数组中的？为什么不能按照需要的顺序直接放置呢？ - rdelmar

@rdelmar 在数组初始化后的某个未知时间添加了这些点。初始化时数组中仅有四个角落的点。 - lobianco

@CleverError：是的，这些点将始终互相成直角。我已经将这个小提示添加到问题中了。谢谢！ - lobianco

你没有提供足够的信息来回答这个问题——在这个特定的例子中，你可以将新的一组点插入到索引1之后（假设A是索引0，B是1等），而不是将它们附加到末尾。但我想这只是一个例子，你需要更多关于一般情况的说明。新的点总是会在b和c之间插入吗？新的一组点本身是否按正确顺序排列？等等。 - rdelmar

@inwit 1)是的，2)是的，3)有描边的轮廓会更好，但不是绝对必要的。我已经在问题中添加了备选布局。 - lobianco

Answer 1

我认为这可能会行。我用几组数字进行了测试，看起来它可以工作。基本上，我从索引0开始（任何起始点都应该可以），将其添加到arrangedPoints数组中，然后查找具有相同y值的最近点--该点被添加到arrangedPoints并从原始randomPoints数组中删除。然后我在x方向上做同样的事情，并重复此过程，直到randomPoints数组中只剩下一个点，并将其添加到arrangedPoints的末尾。

-(void)arrangePoints:(NSMutableArray *) randomPoints {
    NSMutableArray *arrangedPoints = [NSMutableArray array];
    [arrangedPoints addObject:[randomPoints objectAtIndex:0]];
    [randomPoints removeObjectAtIndex:0];

    while (randomPoints.count > 1) {
        //Look for the closest point that has the same y value
        int yValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].y;
        int xValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].x;
        NSIndexSet *indSet = [randomPoints indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop){
            return yValueOfknownPoint == [obj CGPointValue].y;
        }];
        NSLog(@"%d",indSet.count);

        if (indSet.count == 1) {
            [arrangedPoints addObject:[randomPoints objectAtIndex:indSet.firstIndex]];
            [randomPoints removeObjectAtIndex:indSet.firstIndex];
        }else{
            __block int min = 10000000;
            __block int foundIndex;
            [indSet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) {
                int posibleMin = fabs(xValueOfknownPoint - [[randomPoints objectAtIndex:idx]CGPointValue].x);
                if (posibleMin < min) {
                    min = posibleMin;
                    foundIndex = idx;
                }
            }];
            [arrangedPoints addObject:[randomPoints objectAtIndex:foundIndex]];
            [randomPoints removeObjectAtIndex:foundIndex];
        }

        //Look for the closest point that has the same x value
        xValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].x;
        yValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].y;
        indSet = [randomPoints indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop){
            return xValueOfknownPoint == [obj CGPointValue].x;
        }];

        if (indSet.count == 1) {
            [arrangedPoints addObject:[randomPoints objectAtIndex:indSet.firstIndex]];
            [randomPoints removeObjectAtIndex:indSet.firstIndex];
        }else{
            __block int min = 10000000;
            __block int foundIndex;
            [indSet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) {
                int posibleMin = fabs(yValueOfknownPoint - [[randomPoints objectAtIndex:idx]CGPointValue].y);
                if (posibleMin < min) {
                    min = posibleMin;
                    foundIndex = idx;
                }
            }];
            [arrangedPoints addObject:[randomPoints objectAtIndex:foundIndex]];
            [randomPoints removeObjectAtIndex:foundIndex];
        }
    }
    [arrangedPoints addObject:randomPoints.lastObject];
    NSLog(@"%@",arrangedPoints);

}

针对已知问题，以下是一些补充点：

对于像G和M这样的等距点，我认为我会将点集分开处理 - 而不是将所有东西都放到一个数组中，我会保留原始矩形和每个新的点集分开。然后，在构建路径时，我只会寻找自己点集或原始矩形内的点，而不会在任何其他点集中寻找。

为了解决inwit提出的问题，即重复折返的问题，我认为您需要确定一组点是否与边缘或角落相交 - 我认为只有角落才会出现这个问题。您可以通过检查两个点是否落在原始矩形的两条不同线上（而不是同一条线上）来检查角落。然后，您需要计算缺失的点（例如上面最后一个示例中的虚拟点p），并查看它与原始矩形的哪个点相同，然后从路径中删除该点。我认为我的算法将能够正常工作。

- rdelmar

---

你的方法是否适用于上面 其他可能的布局 中的最后一个图形，其中被取出的块是原始矩形的一个角落中的较小矩形？这个较小的矩形将与原始矩形共享一个公共点，即前面提到的左上角点。 - inwit

我认为是这样的，因为我的方法没有任何关于原始矩形的概念。它只是沿着x方向寻找最近的点，然后是y方向 - 所有点都可以是随机顺序的。 - rdelmar

以下是一个测试用例，用于测试您的方法。它是由8个点组成的，前4个代表原始矩形，后4个代表从其中一个角落移除的较小矩形。(0, 0), (10, 0), (10, 10), (0, 10), (10, 9), (10, 10), (9, 10), (9, 9)。（请注意，点(10, 10)是退化的，即在列表中出现两次。我认为这会导致路径“双倍回来”，这对填充不是问题，但会导致突出的笔画。） - inwit

我可以不用检查就知道那组点会引起问题。另外，在上面的第一个示例中，在“其他可能的布局”中，如果我的方法到达点m并且点n和g与其等距离，则它将选择数组中的第一个点。没有办法解决这些问题，除非进一步制定规则。 - rdelmar

我喜欢这种方法 - 我会试一试。你对于你指出的不足有什么解决方案建议（例如，与某个点等距离的点）？ - lobianco

我在我的帖子中添加了一些额外的评论，以解决我提到的一些问题和@inwit提出的问题。 - rdelmar

Answer 2

以下���一种方法（伪代码），如果您只对填充而不是描边感兴趣：

1. 使用 CGPathCreateMutable() 创建一个空的可变路径。
2. 将原始矩形图形作为封闭循环添加到可变路径中。
3. 逐个将每个附加的不规则图形作为封闭循环单独添加到可变路径中。
4. 使用函数 CGContextEOFillPath() 使用奇偶填充规则填充侵蚀的图形。

在Quartz 2D编程指南的填充路径部分中描述了奇偶填充规则。

您可能还会对此内容感兴趣。

- inwit

---

感谢inwit。笔画可能是必要的，但点赞为奇偶填充规则提供的信息。 - lobianco

你是否需要使用奇偶填充规则？如果你只是用背景色填充额外的封闭图形，那么它应该会给你想要的填充侵蚀图形（不是吗？）。 - rdelmar

Answer 3

好的，这个算法可能看起来很复杂（而且远非最优），但我会这样处理。

1. Find the point(s) with lowest X-value

2. Of those points find point P (using a loop) such that:
    - P has a nabour N with the same X-value
    - There exists no other point that vertically lies between P and its nabour N with the same Y value
    (if no P exists with a nabour, the algorithm has ended, after joining P with its horizontally aligned point)

3. If there exists a point with the same X value as P (horizontally aligned), join that point and P with a line.

4. Now join point P with its nabour N

5. Find all points with the same X-value as N (horizontally aligned)

6. Goto 2

希望它能正常工作（尚未测试）。

- v1Axvw