Упорядочивая перетасованные точки, которые могут быть соединены для формирования многоугольника (в python)

У меня есть набор точек, которые соединяются, чтобы сформировать многоугольник в двумерном декартовом пространстве. Он находится в виде списка кортежей 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.000000250000025, -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)]

Точки:

Плохой порядок точек приводит к:

Правильный способ подключения:

Есть ли хороший (и простой, если возможно) алгоритм, чтобы изменить порядок точек на правильный порядок? `

Ответ 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()

Ответ 2

Я написал статью об обобщении вашей проблемы давно. Здесь есть приятное описание , созданное для класса в вычислительной геометрии. Обобщение заключается в том, что алгоритм работает, даже если ваш многоугольник имеет отверстия; Смотри ниже. Если у него нет отверстий, он по-прежнему работает без изменений.

J. О'Рурк, "Единственность ортогональных связных точек", Вычислительная морфология, Г. Т. Toussaint (редактор), Elsevier Science Publishers, B.V. (North-Holland), 1988, 99-104.