以 Python 编写的将打乱顺序的点按顺序连接成多边形的算法

Question

我有一组点，它们连接成一个在2D笛卡尔空间中的多边形。它是以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.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)]

这些点：

错误的顺序结果为：

正确连接方式：

是否有任何好的（如果可能）算法来重新排序点以获得正确的顺序？`

- user5198

---

这不是最通用的解决方案，但您是否尝试将每个点连接到最近的邻居？ - Lev Levitsky

也可以看一下这个，或者这个。 - Lev Levitsky

那么“正确的顺序”是什么？ - Bart Kiers

是的，我尝试过将点连接到最近的邻居。但这并没有起作用。因为虽然存在最近的点，但当我们将它们连接起来时，会导致交叉或者不太接近但应该被连接在一起的点。 - user5198

@BartKiers 为正确加入的顺序制作了一张 Inkscape 图表。 - user5198

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()

- eudoxos

Answer 2

我使用了最近邻方法来完成。所以，这个想法是从起始点列表中选择一个点作为起始点（在这个脚本中我选择了第一个点），将其添加到一个新列表中，用于存储有序的点，然后使用公式np.sqrt((x1-x2)**2 + (y1-y2)**2)检查其最近邻。然后选择最近的点，将其添加到第二个列表中，检查其最近邻，并验证该最近邻是否已经在列表中。如果是，则继续检查第二个点，验证它是否在第二个列表中，以此类推。当所有点都被添加到第二个列表中时，算法结束。以下是代码：

import numpy as np
import matplotlib.pyplot as plt


start_lst = [(-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)]
listx = [point[0] for point in start_lst]
listy = [point[1] for point in start_lst]

plt.plot(listx,listy)
plt.show()

start_point = listx[0], listy[0]
sorted_points = []
while len(start_point)>0:
    sorted_points.append(start_point)
    x1, y1 = start_point
    dists = {(x2, y2): np.sqrt((x1-x2)**2 + (y1-y2)**2) for x2, y2 in zip(listx, listy)}
    dists = sorted(dists.items(), key=lambda item: item[1])
    for dist in dists:
        if dist[0] not in sorted_points: 
            start_point = dist[0]
            break
        if dist == dists[-1]:
            start_point = ()
            break

xs = [point[0] for point in sorted_points]
ys = [point[1] for point in sorted_points]
plt.plot(xs,ys)
plt.show()

- Aelius

---

我使用了你上面的答案，结果接近我所需的。对于多边形来说，有些点仍然出现问题。在应用了上面的答案后，我使用了你的解决方案，它起作用了。所以，谢谢你的帮助。将每个答案结合起来是我的解决方案。 - Zx4161

我使用了你上面的答案，结果对我所需的东西来说很接近。多边形的一些点仍然出现问题。我在应用了上面的答案后使用了你的解决方案，它起作用了。所以，谢谢你。结合每个答案就是我的解决方案。 - undefined