如何在Python中正确排序点集以构建多边形？

我有一组x、y坐标数据，想要构建一个多边形来表示这些数据，需要先正确排序点集，让多边形连线绘制准确。尝试了基于均值点计算角度并排序的代码，但结果不符合预期，请问在Python中该怎么实现？

相关说明 #

• 预期效果：得到一个闭合、轮廓规整的多边形
• 当前错误效果：连线交叉、轮廓混乱的多边形
• 尝试的代码：

mean = np.mean(data, axis=0)
# Compute angles
angles = np.arctan2((data-mean)[:, 1], (data-mean)[:, 0])
# Transform angles from [-pi,pi] -> [0, 2*pi]
angles[angles < 0] = angles[angles < 0] + 2 * np.pi
# Sort
sorting_indices = np.argsort(angles)
sorted_data = data[sorting_indices]

问题原因 #

你当前的方法基于全局均值点计算极角排序，当点集中包含内部点或者点集不是凸多边形时，这种排序方式会导致连线交叉——内部点的极角会和外围点混在一起，打乱了轮廓的顺序。

解决方案 #

情况1：点集包含内部点，提取外围凸包

如果数据里存在内部点，想要得到规整的多边形轮廓，需要先提取所有点的凸包（最外围的顶点集合），凸包算法会自动按顺序排列顶点：

import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt

# 加载数据（假设data是shape为(n,2)的numpy数组）
data = np.loadtxt("你的数据文件路径")

# 计算凸包
hull = ConvexHull(data)
# 获取排序后的凸包顶点
sorted_hull_points = data[hull.vertices]

# 绘制结果（闭合多边形）
plt.plot(np.append(sorted_hull_points[:,0], sorted_hull_points[0,0]),
         np.append(sorted_hull_points[:,1], sorted_hull_points[0,1]), 'r-')
plt.scatter(data[:,0], data[:,1], c='b')
plt.show()

情况2：所有点都是多边形顶点（无内点）

如果所有点都是多边形的顶点，只是顺序混乱，应该用最低点作为基准点计算极角排序，而非全局均值点，这样能避免凹多边形的排序错误：

import numpy as np
import matplotlib.pyplot as plt

data = np.loadtxt("你的数据文件路径")

# 找到y坐标最小的点（若有多个，选x最小的）
min_y_idx = np.argmin(data[:,1])
base_point = data[min_y_idx]

# 计算所有点相对于基准点的向量
vectors = data - base_point

# 计算极角
angles = np.arctan2(vectors[:,1], vectors[:,0])

# 按极角排序
sorted_indices = np.argsort(angles)
sorted_data = data[sorted_indices]

# 绘制闭合多边形
plt.plot(np.append(sorted_data[:,0], sorted_data[0,0]),
         np.append(sorted_data[:,1], sorted_data[0,1]), 'r-')
plt.scatter(data[:,0], data[:,1], c='b')
plt.show()

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