objective-c - iOS-順序付けされていないCGPointを使用して特定のCGPathを描画する方法

Question

このASCII図面を考えてみましょう。

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

ポイントA、B、C、およびDは、CGPoints内で既知であり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、、、... 、、から線を引く必要があります。配列内でEがBの後になく、CがLの後にない場合（これはそうではありません）、これは明らかに正しく描画されません。B → EE → FK → LL → CC → D

詳しくは

1. すべての線は互いに垂直に描かれているので、すべての線はそれらの前後でまたは座標をCGPoints共有する必要があります。xyCGPoint
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

ストロークではなく塗りつぶしだけに関心がある場合の1つのアプローチ（擬似コード）は次のとおりです。

1. を使用して空の可変パスを作成しますCGPathCreateMutable()。

2. 元の長方形の図形を閉ループとして可変パスに追加します。

3. 閉じたループとして、追加の不規則な図形を1つずつ可変パスに個別に追加します。

4. この関数を使用して、偶数奇数の塗りつぶしルールCGContextEOFillPath()を使用して侵食された図形を塗りつぶします。

偶数奇数の塗りつぶしルールについては、の「パスの塗りつぶし」セクションで説明していQuartz 2D Programming Guideます。

あなたもこれに興味があるかもしれません

Answer 2

私はこれがそれをするかもしれないと思います。私はそれをいくつかの数字のセットでテストしました、そしてそれはうまくいくようでした。基本的に、インデックス0のポイントから開始し（任意の開始ポイントが機能するはずです）、それをarrangedPoints配列に追加してから、同じy値を持つ最も近いポイントを探します。そのポイントはarrangedPointsに追加され、元のrandomPointsから削除されます。配列。次に、x方向で同じことを行い、randomPoints配列にポイントが1つだけ残るまで繰り返し、それを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);

}

既知の問題に対処するためのいくつかの追加ポイント：

NからGやMのような等距離の点を処理するには、点のセットを別々に保つと思います。すべてのものを1つの配列に入れるのではなく、元の長方形と、別々になる新しい点のセットをそれぞれ保持します。 。次に、パスを作成するときに、自分のポイントのセットまたは元の長方形内のポイントのみを検索し、他のポイントのセットは検索しませんでした。

持ち上がった問題に対処するには、それ自体を2倍にするという、一連のポイントが側面と交差するかコーナーと交差するかを判断する必要があると思います。コーナーの問題だけがその問題を提示すると思います。2つのポイントが（同じ線ではなく）元の長方形の2つの異なる線上にあることを確認することで、コーナー1を確認できます。次に、欠落しているポイント（上記の最後の例では推定ポイントp）を計算し、元の長方形のどのポイントも同一であるかを確認してから、そのポイントをパスから削除する必要があります。そうすれば、私のアルゴリズムは正しく機能すると思います。

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

私はそれがうまくいくことを願っています（それをテストしていません）。