How to sort a collection of points so that they set up one after another?

Question

I have an ArrayList which contains coordinates of points:

class Point
{
   int x, y;
}
ArrayList<Point> myPoints;

of such an image for example:

The problem is that these points are set chaotically in the ArrayList and I would like to sort them so that 2 points lying next to each other on the image are also one after another in the ArrayList. I can't come up with some good idea or algorithm to solve such a sorting... Are there some known methods of solving such problems?

edit: The shape cannot cross over itself and let's assume that only shapes looking similarly like this can occur.

Answer 1

My thinking is that you first need a mathematical definition of your ordering. I suggest (Note, this definition wasn't clear in the original question, left here for completeness):

Starting with placing any point in the sequence, then perpetually append to the sequence the point closest to the current point and that hasn't already been appended to the sequence, until all points are appended to the sequence.

Thus with this definition of the ordering, you can derive a simple algorithm for this

ArrayList<point> orderedList = new ArrayList<point>();

orderedList.add(myList.remove(0)); //Arbitrary starting point

while (myList.size() > 0) {
   //Find the index of the closest point (using another method)
   int nearestIndex=findNearestIndex(orderedList.get(orderedList.size()-1), myList);

   //Remove from the unorderedList and add to the ordered one
   orderedList.add(myList.remove(nearestIndex));
}

The above is pretty universal (regardless of the algorithm for finding the next point). Then the "findNearestIndex" method could be defined as:

//Note this is intentially a simple algorithm, many faster options are out there
int findNearestIndex (point thisPoint, ArrayList listToSearch) {
    double nearestDistSquared=Double.POSITIVE_INFINITY;
    int nearestIndex;
    for (int i=0; i< listToSearch.size(); i++) {
        point point2=listToSearch.get(i);
        distsq = (thisPoint.x - point2.x)*(thisPoint.x - point2.x) 
               + (thisPoint.y - point2.y)*(thisPoint.y - point2.y);
        if(distsq < nearestDistSquared) {
            nearestDistSquared = distsq;
            nearestIndex=i;
        }
    }
    return nearestIndex;
}

Update: Since the question was revised to largely adopt the definition I used, I took out some of the caveats.