如何将随机分布的点数组排序为对应形状的连续点序列

我有一组随机分布的点数组，这些点可构成一个带凹面的不规则闭合形状，但组成该形状的点（坐标）在数组中是随机分布的。需要对这些点进行排序，使得数组中每对连续点对应形状中的连续点。

此前尝试过的方法均失效：

• 基于点的顺时针排序：在边缘和后方直线处失效
• 以X值最小的点为起点，依次添加最近点：边缘处失效（最近点未必是连续点）
• 以X值最小点的Y值为分界，拆分上下部分分别排序：凹面部分导致该方法失效

点存储在.dat文件中，每行包含两个以空格分隔的数字，示例格式：

2.345 1.234
1.234 2.345

可行解决方案 #

针对带凹面的不规则多边形，单纯依赖全局角度或最近邻的排序逻辑容易失效，推荐以下混合方法：

方法1：特征点起始+方向追踪排序 #

1. 确定可靠起始点：选X值最小的点（若有多个则选Y值最小的），这个点属于形状的凸顶点，不会在凹面区域，避免初始方向出错。
2. 确定初始前进方向：从起始点出发，找到除起始点外X值最小的点作为第一个邻接点，确定初始的前进向量（如果形状有明确的起始边，也可以直接指定）。
3. 迭代追踪连续点：
   • 对当前点P，遍历所有未选中的点，计算每个点Q相对于当前前进向量的相对夹角（而非全局坐标系的角度）。
   • 筛选出夹角最小的3-5个候选点（避免被凹面内的点干扰）。
   • 在候选点中选择：如果当前处于直线段，选距离P最远的点；如果是转弯区域，选夹角变化符合形状趋势的点。
   • 更新前进向量为P到选中点的方向，重复直到所有点被选中。

方法2：凸壳+凹点插入排序（适合编程实现） #

如果需要写代码自动化处理，这个方法更严谨：

1. 提取凸壳：用Graham扫描或Andrew算法计算点集的凸壳，得到凸顶点的连续顺序。
2. 定位凹点的插入位置：每个凹点必然位于凸壳某条边的内侧，计算凹点到该边的投影位置，按投影距离从近到远排序后，插入到凸壳对应边的两个顶点之间。
3. 拼接完整顺序：将所有凸点和插入后的凹点拼接，得到符合形状连续顺序的点数组。

.dat文件处理流程 #

1. 读取文件：逐行读取内容，将每行的两个数值转换为坐标元组（如(x, y)），存入列表。
2. 去重：移除列表中的重复点（如果存在）。
3. 排序：用上述任一方法对列表排序。
4. 输出：将排序后的点按每行两个数值的格式写入新的.dat文件。

内容的提问来源于stack exchange，提问作者Lucas Pelizzari