如何对一组点进行排序,使它们一个接一个地设置？

Question

我有一个包含点坐标的ArrayList:

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

这样的图像例如:

问题是这些点在ArrayList中混乱地设置,我想对它们进行排序,使得在图像上彼此相邻的2个点也在ArrayList中一个接一个.我无法想出一些好的想法或算法来解决这样的排序......是否有一些已知的方法来解决这些问题？

编辑:形状不能越过自己,让我们假设只有像这样的形状才会出现.

Answer 1

我的想法是你首先需要对你的排序进行数学定义.我建议(注意,这个定义在原始问题中并不清楚,为了完整性留在这里):

从在序列中放置任何点开始,然后永久性地将序列附加到最接近当前点并且尚未附加到序列的点,直到所有点都附加到序列.

因此,通过这种排序定义,您可以为此派生一个简单的算法

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

以上是非常普遍的(无论找到下一个点的算法如何).然后"findNearestIndex"方法可以定义为:

//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;
}

更新:由于问题被修改为主要采用我使用的定义,我拿出了一些警告.