Algorithm for ordering points on a map?

Question

I have an array of points, where each point is a coordinate on a map. I'd like to make it so that when I add a point to the map, it's added to my array in between the closest two points.

Additionally, I'd like to render the points, so that there are never any crossovers between the different points. New points should be added to the outside edge of the resulting polygon, and connected to the closest two.

Is there an algorithm for doing this?

Edit:

For clarity, I have the following screenshot. I'd like to achieve method B:

Edit 2:

Here's a bunch of code I wrote to try and solve the problem. Assume that MBCoordinates are just that, coordinates:

//
//  Detect which coordinate is the closest to the supplied coordinate
//

- (void) insertCoordinateBetweenClosestNeighbors:(MBCoordinate *)coordinate{

if (![self points] || [[self points] count] < 3) {
    [[self points] addObject:coordinate];
    return;
}

NSMutableSet *pointSet = [NSMutableSet setWithArray:[self points]];

MBCoordinate *closestCoordinate = [self closestCoordinateToCoordinate:coordinate inSet:pointSet];
[pointSet removeObject:closestCoordinate];

MBCoordinate *nextClosestCoordinate = [self closestCoordinateToCoordinate:coordinate inSet:pointSet];

NSUInteger indexOfClosestCoordinate, indexOfSecondClosestCoordinate, insertionIndex;


for (NSUInteger i=0; i < [[self points] count]; i++) {

    if ([[self points][i] isEqual:closestCoordinate]) {
        indexOfClosestCoordinate = i;
    }

    if ([[self points][i] isEqual:nextClosestCoordinate]) {
        indexOfSecondClosestCoordinate = i;
    }
}

if(indexOfSecondClosestCoordinate == indexOfClosestCoordinate-1){
    insertionIndex = indexOfSecondClosestCoordinate+1;
}else{
    insertionIndex = indexOfClosestCoordinate+1;
}

[[self points] insertObject:coordinate atIndex:insertionIndex];

 /*

 Not in use in my program, but an alternate attempt:
[[self points] addObject:coordinate];
[self sortPointsByDistance];
 */
}

- (void) sortPointsByDistance{

//
//  Points that need sorting
//

NSMutableSet *unprocessedPoints = [NSMutableSet setWithArray:[self points]];

//
//  All of the unsorted points
//

NSMutableSet *unsortedPoints = [NSMutableSet setWithArray:[self points]];

//
//  The unsorted points minus the closest one
//

NSMutableSet *unsortedPointsExceptClosest = [NSMutableSet setWithArray:[self points]];

//
//  We put the point into here in the correct order
//

NSMutableArray *sortedPoints = [@[] mutableCopy];


//
//  Prime the pump
//

MBCoordinate *workingCoordinate = [self points][0];
[sortedPoints addObject:workingCoordinate];
[unprocessedPoints removeObject:workingCoordinate];

while([unprocessedPoints count] > 0){

    MBCoordinate *closestCoordinate = [self closestCoordinateToCoordinate:workingCoordinate inSet:unsortedPoints];
    MBCoordinate *secondClosestCoordinate = nil;

    //
    //  The closest point might be sorted already!
    //
    //  If it is, then we have to find the closest point.
    //

    if ([sortedPoints containsObject:closestCoordinate]) {

        NSInteger indexOfClosest = [sortedPoints indexOfObject:closestCoordinate];
        NSInteger indexOfSecondClosest = indexOfClosest;
        NSInteger targetIndex = indexOfClosest+1;

        if (!secondClosestCoordinate) {
            [unsortedPoints removeObject:closestCoordinate];
            secondClosestCoordinate = [self closestCoordinateToCoordinate:workingCoordinate inSet:unsortedPointsExceptClosest];

            if ([sortedPoints containsObject:secondClosestCoordinate]) {

                //
                //  Insert between the two points
                //

                indexOfSecondClosest = [sortedPoints indexOfObject:secondClosestCoordinate];

            }
        }

        if (indexOfSecondClosest < indexOfClosest) {
            targetIndex = indexOfSecondClosest + 1;
        }

        [sortedPoints insertObject:workingCoordinate atIndex:targetIndex];
        workingCoordinate = [unprocessedPoints anyObject];

        break;

    }else{
        workingCoordinate = closestCoordinate;
    }

    [sortedPoints addObject:workingCoordinate];
    [unprocessedPoints removeObject:workingCoordinate];
    unsortedPointsExceptClosest = [unsortedPoints copy];
    secondClosestCoordinate = nil;

}

[self setPoints:sortedPoints];
}

- (MBCoordinate *) closestCoordinateToCoordinate:(MBCoordinate *)coordinate inSet:(NSSet *)aSet{

MBCoordinate *closest = nil;
CGFloat closestDistance;

for (MBCoordinate *coordinateInSet in aSet) {

    if ([coordinateInSet isEqual:coordinate]) {
        continue;
    }

    if (!closest) {
        closest = coordinateInSet;
        closestDistance = [self distanceBetweenCoordinate:coordinate andCoordinate:coordinateInSet];
    }

    CGFloat distanceBetweenPoints = [self distanceBetweenCoordinate:coordinate andCoordinate:coordinateInSet];

    if (distanceBetweenPoints < closestDistance) {
        closest = coordinateInSet;
        closestDistance = distanceBetweenPoints;
    }


}

return closest;
}

//
//  Determines the distance between two coordinates
//

- (CGFloat) distanceBetweenCoordinate:(MBCoordinate *)coordinate andCoordinate:(MBCoordinate *)anotherCoordinate{

CGFloat xDistance, yDistance;

xDistance = coordinate.latitude-anotherCoordinate.latitude;
yDistance = coordinate.longitude-anotherCoordinate.longitude;

float distance = xDistance/yDistance;

//
//  Absolute value of floats...
//


if (distance < 0) {
    distance *= -1;
}

return distance;

}

Answer 1

Well, I don't know how your coordinate system works, but what you want to do is calculate the Euclidean Distance between your new point and the other points in the array. Then just insert your new point between the two that have the shortest euclidean distances to your new point.

Just keep in mind that the surface of the Earth is not flat. The Euclidean distance linked above assumes flatness in two dimensions. So the farther apart your points are, the less accurate that formula will be.

Answer 2

I think that what you are after can be achieved through the use of a Convex Hull. This will create a polygon whose sides go around all your points. However, should you have a point which is not on the edge, it will end up within the polygon.

You can check out an implementation of the Convex Hull algorithm on this page.