问题描述

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

I have a collection of points that join to form a polygon in 2D cartesian space. It is in the form of a python list of tuples

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

问题在于将它们连接起来并在图中形成一个多边形.(我正在使用 matplotlib.path)

the problem is the join them and form a polygon in a graph. (I'm using matplotlib.path)

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

I made a function to do this. It works as follows:

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

it goes to first point ie (x1, y1) and joins a line to next point ie (x2, y2) and a line from (x2, y2) to (x3, y3) and so on .. till the end which is (xn, yn). It closes the polygon by joining (xn, yn) to (x1, y1).

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

The problem is the list containing these points does not contain the points in the right order so that results in bad drawings like these(Every closed polygon is colored automatically).

示例:

对于这个顶点列表 = `[(-0.500000050000005, -0.5), (-0.499999950000005, 0.5), (-0.500000100000005, -1.0), (-0.49999990000000505, 1.0), (0.500)1.0000000250000025,0.5)(1.0000000250000025,0.0.5)，(0.49999950000005,0.5)(0.0.999999750000024,0.5)，(0.99999750000024,0.5)，(0.500000100000005,0.1.0)，(0.49999000000000505,1.0)，(-1.0,0.0), (-0.0, -1.0), (0.0, 1.0), (1.0, 0.0), (-0.500000050000005, -0.5)]

for this list of vertices = `[(-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)]

要点:

错误的点顺序会导致:

正确的加入方式:

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

Is there any good (and easy if possible) algorithm to reorder the points to correct order? `

推荐答案

这会根据极坐标对你的点进行排序:

This sorts your points according to polar coordinates:

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