objective-c - 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

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 等点与 N 的等距点，我想我会将点集分开——而不是将所有东西都放入一个数组中，我会保留原始矩形，以及每个新的点集分开来。然后当我构建路径时，我将只在我自己的点集或原始矩形中寻找点，而不是在任何其他点集中。

要处理智能提出的问题，即加倍自身，我认为您必须确定一组点是否与边或角相交——我认为只有角点会出现该问题。您可以通过查看其中 2 个点落在原始矩形的 2 条不同线上(而不是在同一条线上)来检查角点。然后，您必须计算缺失点(上面最后一个示例中的假定点 p)并查看原始矩形的哪个点也相同，然后从路径中删除该点。我认为我的算法会正常工作。