Как нарисовать самый большой многоугольник из набора точек

Question

Итак, у меня есть набор точек (x, y), и я хочу иметь возможность нарисовать самый большой многоугольник с этими точками в качестве вершин. Я могу использовать patches.Polygon () в matplotlib, но это просто рисует линии между точками в порядке, который я им даю. Это не делает автоматически то, что я хочу. Например, если вы хотите нарисовать квадрат и отсортировать точки, увеличив х, а затем увеличив у, я получу не квадрат, а два соединительных треугольника. (строка «пересекает»)

Таким образом, проблема сейчас состоит в том, чтобы найти способ сортировки списка точек так, чтобы при обходе этого списка я "обходил" многоугольник.

Или, может быть, в Matplotlib есть какие-то другие функции, которые могут сделать это для меня?

Answer 1

Как и предполагалось, все готовое простое решение состоит в том, чтобы вычислить углы от некоторой внутренней точки до всех точек и отсортировать их.

Итак, вот вам функция numpy для вычисления ccworder:

In []: def ccworder(A):
   ..:     A= A- mean(A, 1)[:, None]
   ..:     return argsort(arctan2(A[1, :], A[0, :]))
   ..:

И простая демонстрация:

In []: A
Out[]:
array([[0, 0, 1, 1],
       [0, 1, 1, 0]])
In []: ccworder(A)
Out[]: array([0, 3, 2, 1])

Обновление:
Может показаться, что такой порядок может быть утомительным для вычисления, но numpy может обеспечить хорошую абстракцию, чтобы сделать их довольно простыми.

Предупреждение: Как Джодругие отмечали, что ccworder будет формировать правильный порядок на выпуклой оболочке, только если все точки готовы на выпуклой оболочке.Т.е. как-то порядок отсутствует, так как, похоже, это случай ОП, его можно восстановить.Конечно, есть и другие ситуации, когда ccworder используется полностью.

Answer 2

Тогда, как насчет сортировки самостоятельно?

Скажем, набор точек выпуклой оболочки хранится в виде списка точек в Python, а C - это своего рода внутренняя точка в наборе точек выпуклой оболочки. подготовьте компаратор, например, следующий псевдокод:

def cmpAngle(p1, p2):
    vector1 = p1 - C
    vector2 = p2 - C
    return dotProduct(vector1, vector2)
points.sort(cmp=cmpAngle)

Идея состоит в том, чтобы использовать точечное произведение для определения порядка их относительного вращения.

Answer 3

Из ваших комментариев к другим ответам вы, похоже, уже получили набор точек, определяющих выпуклую оболочку, но они не упорядочены. Самый простой способ их упорядочить - взять точку внутри выпуклой оболочки в качестве начала новой системы координат. Затем вы преобразуете (наиболее вероятно) декартовы координаты ваших точек в полярные координаты относительно этого нового кадра. Если вы упорядочите свои точки относительно их координаты полярного угла, вы можете нарисовать выпуклый корпус. Это верно только в том случае, если множество ваших точек определило выпуклую (не вогнутую) оболочку.

Answer 4

Если вы уже знаете точки корпуса , то рисование многоугольника путем соединения этих точек на самом деле довольно просто сделать в Matplotlib, поскольку многоугольники реализованы в Matplotlib как paths . Я бы начал с matplotlib.path класса .

Если вы не знаете точек корпуса, я согласен с Эльмаром - выпуклый корпус - это тот алгоритм, который вам нужен. Я закодировал этот алгоритм в NumPy и построил его в Matplotlib. Мой код был заимствован из превосходного рецепта в Кулинарной книге SciPy, здесь . Этот рецепт включает реализацию NumPy плюс полный код, необходимый для построения в Matplotlib выпуклой оболочки вокруг заданного набора точек.

Кроме того, Matplotlib включает пакет под названием delauney , который, как вы могли догадаться, предназначен для тесселяции поверхности с использованием триангуляции Делоне. И, как вы, возможно, знаете, это связано с выпуклой оболочкой посредством тесселяции вороной - то есть границы каждой ячейки вороной создаются из расчета выпуклой оболочки.

Answer 5

Я не знаю Matplotlib, но вам нужно / нужно нарисовать выпуклую оболочку из набора точек. Думайте о выпуклом корпусе как о эластичной веревке, которую вы помещаете вокруг набора точек. Форма, которую принимает эластичная веревка, является выпуклой оболочкой. Существуют разные алгоритмы вычисления выпуклой оболочки, поэтому проверьте, поддерживает ли Matplotlib какой-либо из них. Если нет, проверьте эти ссылки для начала того, как их реализовать.

http://en.wikipedia.org/wiki/Convex_hull

http://en.wikipedia.org/wiki/Convex_hull_algorithms

Answer 6

Здесь у вас есть реализация Python выпуклой оболочки (это то, что вы ищете):

http://www.scipy.org/Cookbook/Finding_Convex_Hull

Answer 7

Я использовал scipy.spatial для такого рода проблем. Имеет специальные функции для построения выпуклых оболочек. Смотрите здесь . Может быть, это больше огневой мощи, чем вы хотели.