排序可以连接形成多边形的混洗点（在python中） [英] ordering shuffled points that can be joined to form a polygon (in python)

问题描述

我有一组点加入到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.0，-1.0），（0.0,0.0），（-0.99999750000024,0.5），（0.9999999750000024,0.5），（0.500000100000005，-1.0），（0.49999990000000505,1.0），（ - 1.0,0.0） ，（1.0,0.0），（-0.500000050000005，-0.5）]

要点：

错误的点数导致：

正确的加入方式：

是否有任何好的（并且如果可能，简单的话）算法将点重新排列成正确的顺序？
`

解决方案

这样按照极坐标排序：

 导入数学
导入matplotlib.patches作为修补程序
导入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.999999950000005,0.5） （1.0,0.0），（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）] 
＃计算质心
 cent =（sum（[p [0] for p in pp]）/ len（pp），sum（[p [1] for p in pp]）/ len（pp））
＃按极角排序
 pp.sort（key = lambda p：math.atan2（p [1] -cent [1]，p [0]  - 分[0]））
＃绘图点
 pylab.scatter（[p]中的p [p]，[p]中的p [p]）
＃plot polyline 
 pylab.gca（）。add_patch（patches.Polygon（pp，closed = False，fill = False））
 pylab.grid（）
 pylab.show（）
  

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

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:

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

Example:

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

The points:

Bad order of points results in:

Correct way to join:

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

这篇关于排序可以连接形成多边形的混洗点（在python中）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！