7

考虑这个 ASCII 绘图：

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

点 A、B、C 和 DCGPoints在 an中是已知的NSMutableArray，并已用于创建填充的CGPath. 现在考虑这张图：

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

CGPointsE、F、G、H、I、J、K 和 L 是已知的，并已附加到NSMutableArray.

问题

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

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

目前，我可以通过循环创建一个CGPath- 如果我知道 - 的顺序：CGpoints

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共享一个x或y坐标。CGPoint
  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
4

3 回答 3

2

如果您只对填充而不是笔画感兴趣，这是一种方法（在伪代码中）：

  1. 使用创建一个空的可变路径CGPathCreateMutable()。

  2. 将原始矩形图形作为闭环添加到可变路径。

  3. 一个一个地，将每个额外的不规则图形分别添加到可变路径中，作为一个闭环。

  4. 使用该函数使用奇偶填充规则CGContextEOFillPath()填充侵蚀图形。

奇偶填充规则在Quartz 2D Programming Guide.

您可能对此也感兴趣

于 2012-07-21T22:44:33.147 回答
2

我认为这可能会做到这一点。我用几组数字对其进行了测试，它似乎有效。基本上，我从索引 0 处的点开始（任何起点都应该有效），将其添加到排列点数组中，然后查找具有相同 y 值的最近点——该点被添加到排列点并从原始随机点中删除大批。然后我在 x 方向上做同样的事情并重复，直到 randomPoints 数组中只剩下一个点，并将其添加到排列点的末尾。

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

}

解决已知问题的一些补充点：

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

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

于 2012-07-21T23:31:58.513 回答
0

好吧，这似乎是一个非常复杂的算法（而且远非最佳），但我会这样处理它。

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

我希望它有效（尚未测试过）。

于 2012-07-21T19:30:34.647 回答