排序可以连接形成多边形的混洗点(在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)]

要点:

点数不良导致:

正确的加入方式:

是否有任何好的(如果可能的话)简单的算法来重新排序点以正确的顺序？`

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

Answer 2

很久以前,我写了一篇关于你问题概括的文章.有一个很好的desription 这里,在计算几何类创建.总的来说,即使你的多边形有洞,算法仍然有效; 见下文.如果它没有孔,它仍然可以不加修改地工作.
     

J. O'Rourke,"正交连接点的唯一性",Computational Morphology,GT Toussaint(编辑),Elsevier Science Publishers,BV(North-Holland),1988,99-104.