Od Voronoi teselacji do zgrabna wielokątów

Question

z kompletem punktów zbudowałem teselacji Voronoi korzystając scipy:

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

Teraz chciałbym zbudować Polygon in Shapely z regionów algorytm Voronoi stworzonych. Problem polega na tym, że klasa Polygon wymaga listy przeciwnych do ruchu wskazówek zegara wierzchołków. Chociaż wiem, jak order these vertices, nie mogę rozwiązać ten problem, ponieważ często jest to mój wynik:

(nakładających wielokąt). To jest kod (JEDEN PRZYPADKOWY PRZYKŁAD):

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

    # https://stackoverflow.com/questions/1709283/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]) 

Jak mogę rozwiązać ten problem?

Answer 1

Jeśli masz już kolekcję wielokątów, nie musisz ich zamawiać w przedsprzedaży.

Obiekt scipy.spatial.Voronoi ma atrybut ridge_vertices zawierający indeksy wierzchołków tworzących linie grzbietu Voronoi. Jeśli indeks wynosi -1, grzbiet przechodzi w nieskończoność.

Najpierw zacznij od kilku losowych punktów, aby zbudować obiekt Voronoi.

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) 

Można to wykorzystać do budowania kolekcji obiektów Zgrabna LineString.

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

Moduł shapely.ops ma polygonize która zwraca generator dla obiektów Zgrabna wielokąta.

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

Lub jeśli chciał jeden wielobok utworzony z obszaru wyznaczonego przez tesselacji Voronoi można wykorzystać metodę Zgrabna unary_union:

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

Answer 2

Funkcja, którą zaimplementowałeś (order_vertices()), nie może działać w twoim przypadku, ponieważ po prostu zajmuje już uporządkowaną sekwencję współrzędnych, która buduje prostokąt, i odwraca kierunek wielokąta (i może działa tylko z prostokątami ...). Ale masz nie uporządkowaną kolejność współrzędnych

Ogólnie rzecz biorąc, nie można zbudować wielobok z pomocą dowolnej kolejności nie uporządkowanych wierzchołków, ponieważ nie ma to unikalne rozwiązanie dla wklęsłych wielokątów, jak pokazano w poniższym przykładzie: https://stackoverflow.com/a/7408711/4313133

Jednakże, jeśli jesteś pewien, że wielokąty są zawsze wypukły, można zbudować wypukłe kadłuba z tego kodu: https://stackoverflow.com/a/15945375/4313133 (testowane teraz, że pracował dla mnie)

Prawdopodobnie można zbudować wypukłej z scipy również, ale nie testuję go: scipy.spatial.ConvexHull

Answer 3

jak inni powiedziane, to dlatego, że musisz odbudować wielokąty z wynikowych punktów poprawnie na podstawie indeksów. Chociaż masz rozwiązanie, pomyślałem, że powinienem wspomnieć, że istnieje również inny pakiet tesselation obsługiwany przez pypi o nazwie Pytess (Disclaimer: jestem opiekunem pakietu), gdzie funkcja voronoi zwraca wielokąty voronoi w pełni zbudowane dla ciebie.