iOS - How to draw a specific CGPath with unordered CGPoints

Question

Consider this ASCII drawing:

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

Points A, B, C, and D are known CGPoints within an NSMutableArray and have been used to create a filled CGPath. Now consider this drawing:

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

CGPoints E, F, G, H, I, J, K, and L are known and have been appended to the end of the NSMutableArray.

The Question

How can I rearrange all the points within the array to create a CGPath that looks like the drawing below?

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

Currently I have no trouble creating a CGPath - if I know the order of the CGpoints - by looping through them:

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

... but this assumes that a line should be drawn from each point in the array i to the following point i + 1. In the drawing above, lines would have to be drawn from A → B, B → E, E → F ... K → L, L → C, C → D. If E is not after B and C is not after L in the array (which they won't be), then this obviously won't draw correctly.

More Information

1. All lines are drawn perpendicular to each other, so all CGPoints should share an x or y coordinate with the CGPoint before and after them.
2. (An extension of #1) A point will always be at right angles to the points before and after it.
3. It is not possible to predict where the points will occur within the square, and the new set of points may or may not be in order when appended to the end of the array.
4. ...

Other Possible Layouts

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

I think this might do it. I tested it with a couple of sets of numbers and it seemed to work. Basically, I start with the point at index 0 (any starting point should work), add that to the arrangedPoints array and then look for the nearest point with the same y value -- that point is added to arrangedPoints and deleted from the original randomPoints array. I then do the same thing in the x direction and repeat until there's only one point left in the randomPoints array, and add that to the end of 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);

}

Some added points to address known problems:

To deal with equidistant points like G and M from N, I think I would keep the sets of points separate -- rather than putting every thing into one array, I would keep the original rectangle, and each new set of points that come in separate. Then when I was constructing the paths, I wold only look for point within my own set of points or the original rectangle, but not in any other set of points.

To deal with the problem inwit brought up, of doubling back on itself, I think you would have to determine whether a set of points intersects a side or a corner -- I think only the corner ones would present that problem. You could check for a corner one by seeing that 2 of the points fall on 2 different lines of the original rectangle (rather than on the same line). You would then have to calculate the missing point (a putative point p in your last example above) and see which point of the original rectangle it's identical too, and then delete that point from the path. I think that my algorithm would then work correctly.