python - ポリゴンを形成するために結合できるシャッフルされたポイントの順序付け（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()