Coordinate Sorting Algorithm

[Danja]

I have a list of latitude and longitude coordinates which are supposed to trace the outline of a city. Somehow they got scrambled so that they are now out of order. I'd like to write a program to arrange them such that one could follow from one coordinate to the next and trace the perimeter. However, I've run out of ideas for algorithms. What I did so far was a simple search for the nearest coordinate, starting from the first coordinate pair in the array. This produced local regions which worked rather well, but globally there were large jumps as the algorithm ran out of nearby coordinates and was forced to jump across the map.

Is there already a developed algorithm to perform this function?

[OReubens]

if the outline is convex you can find the solution by rubberbanding.

if the outline is concave (it has 'bumps' and 'dents')... there is no single one solution. So finding the actual outline is impossible