python - 排序可以连接形成多边形的打乱点（在python中）

Question

我有一个点集合，它们在二维笛卡尔空间中连接形成一个多边形。它采用 python 元组列表的形式

[(x1, y1), (x2, y2), ... , (xn, yn)]

问题是加入它们并在图中形成一个多边形。（我正在使用 matplotlib.path）

我做了一个函数来做到这一点。它的工作原理如下：

它到达第一个点，即 (x1, y1) 并将一条线连接到下一个点，即 (x2, y2) 和一条从 (x2, y2) 到 (x3, y3) 的线，依此类推......直到结束 ( xn, yn)。它通过将 (xn, yn) 连接到 (x1, y1) 来闭合多边形。

问题是包含这些点的列表不包含正确顺序的点，从而导致像这样的不良绘图（每个封闭的多边形都会自动着色）。

例子：

对于此列表，顶点=`[（ - 0.500000050000005，-0.5），（-0.499999999500005，0.5），（-0.500000100000005，1.0） 0.5），（1.0000000250000025，-0.5），（0.4999999950000005，0.5），（-0.9999999999750000024，0.5），（0.99999999999999750000024，0.5） -0.0, -1.0), (0.0, 1.0), (1.0, 0.0), (-0.500000050000005, -0.5)]

要点：

错误的点顺序会导致：

正确加入方式：

有没有什么好的（如果可能的话也很简单）算法来重新排列点以正确的顺序？`

Answer 1

这会根据极坐标对您的点进行排序：

import math
import matplotlib.patches as patches
import pylab
pp=[(-0.500000050000005, -0.5), (-0.499999950000005, 0.5), (-0.500000100000005, -1.0), (-0.49999990000000505, 1.0), (0.500000050000005, -0.5), (-1.0000000250000025, -0.5), (1.0000000250000025, -0.5), (0.499999950000005, 0.5), (-0.9999999750000024, 0.5), (0.9999999750000024, 0.5), (0.500000100000005, -1.0), (0.49999990000000505, 1.0), (-1.0, 0.0), (-0.0, -1.0), (0.0, 1.0), (1.0, 0.0), (-0.500000050000005, -0.5)]
# compute centroid
cent=(sum([p[0] for p in pp])/len(pp),sum([p[1] for p in pp])/len(pp))
# sort by polar angle
pp.sort(key=lambda p: math.atan2(p[1]-cent[1],p[0]-cent[0]))
# plot points
pylab.scatter([p[0] for p in pp],[p[1] for p in pp])
# plot polyline
pylab.gca().add_patch(patches.Polygon(pp,closed=False,fill=False))
pylab.grid()
pylab.show()