Из тезоделирования Вороного в многоугольники Шапели

из набора точек я построил тесселяцию Voronoi, используя scipy:

from scipy.spatial import Voronoi
vor = Voronoi(points)

Теперь я хотел бы создать Polygon in Shapely из регионов, созданных алгоритмом Вороного. Проблема состоит в том, что для класса Polygon требуется список вершин против часовой стрелки. Хотя я знаю, как упорядочить эти вершины, я не могу решить проблему, потому что часто это мой результат:

(перекрывающий многоугольник). Это код (ОДИН СЛУЧАЙНЫЙ ПРИМЕР):

def order_vertices(l):
    mlat = sum(x[0] for x in l) / len(l)
    mlng = sum(x[1] for x in l) / len(l)

    # /info/820934/how-can-i-sort-a-coordinate-list-for-a-rectangle-counterclockwise
    def algo(x):
        return (math.atan2(x[0] - mlat, x[1] - mlng) + 2 * math.pi) % 2*math.pi

    l.sort(key=algo)
    return l

a = np.asarray(order_vertices([(9.258054711746084, 45.486245994138976),
 (9.239284166975443, 45.46805963143515),
 (9.271640747003861, 45.48987234571072),
 (9.25828782103321, 45.44377372506324),
 (9.253993275176263, 45.44484395950612),
 (9.250114174032936, 45.48417979682819)]))
plt.plot(a[:,0], a[:,1])

Как я могу решить эту проблему?

Ответ 1

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

Объект scipy.spatial.Voronoi имеет атрибут ridge_vertices содержащий индексы вершин, образующих линии хребта Вороного. Если индекс -1 то гребень уходит в бесконечность.

Сначала начните с нескольких случайных точек, чтобы построить объект Вороного.

import numpy as np
from scipy.spatial import Voronoi, voronoi_plot_2d
import shapely.geometry
import shapely.ops

points = np.random.random((10, 2))
vor = Voronoi(points)
voronoi_plot_2d(vor)

Вы можете использовать это для создания коллекции объектов Shapely LineString.

lines = [
    shapely.geometry.LineString(vor.vertices[line])
    for line in vor.ridge_vertices
    if -1 not in line
]

Модуль shapely.ops имеет polygonize которая возвращает генератор для объектов Shapely Polygon.

for poly in shapely.ops.polygonize(lines):
    #do something with each polygon

Или, если вы хотите, чтобы один полигон сформировался из области, заключенной в тесселяцию Вороного, вы можете использовать метод Shapely unary_union:

shapely.ops.unary_union(list(shapely.ops.polygonize(lines)))

Ответ 2

Как говорили другие, это связано с тем, что вы должны правильно перестроить полигоны из результирующих точек на основе индексов. Хотя у вас есть решение, я подумал, что я должен упомянуть, что есть еще один поддерживаемый pypi пакет тесселяции, называемый Pytess (Отказ от ответственности: я сторонник пакета), где функция voronoi возвращает полностью созданные для вас полигоны voronoi.

Ответ 3

Функция, которую вы реализовали (order_vertices()), не может работать в вашем случае, потому что она просто берет уже упорядоченную последовательность координат, которая строит прямоугольник и инвертирует направление многоугольника (и, возможно, работает только с прямоугольниками...). Но у вас есть упорядоченная последовательность координат

Вообще говоря, вы не можете построить многоугольник из произвольной последовательности не упорядоченных вершин, потому что нет единственного решения для вогнутых многоугольников, как показано в этом примере: fooobar.com/info/661125/...

Однако, если вы уверены, что ваши полигоны всегда выпуклые, вы можете создать выпуклый корпус с этим кодом: fooobar.com/info/820932/... (протестирован прямо сейчас, он работал у меня)

Вероятно, вы также можете построить выпуклый корпус с scipy, но я не тестирую его: scipy.spatial.ConvexHull