Utwórz diagram voronoi z segmentów linii

Szukam sposobu na utworzenie diagramu voronoi na podstawie segmentów linii zamiast punktów. Zobacz poniższy przykład (zaczerpnięty z tej prezentacji ).

Idealnie chciałbym coś, co mogę napisać w skrypcie z Pythona, ale akceptowalne byłoby również rozwiązanie korzystające z ArcGIS lub podobnego.

Jedyną biblioteką, która to zrobiła, jaką do tej pory znalazłem , jest openvoronoi , która wygląda obiecująco. Czy są jeszcze jakieś?

My (zespół uniwersytecki) zaprojektowaliśmy do tego implementację za pomocą dodatku ArcGIS 10.0 i ArcObjects. Aplikacja jest całkowicie darmowa. Implementacja wykorzystuje metodologię rastrową, która przyjmuje jako punkty wejściowe, linie lub wielokąty, aby tworzyć zwykłe lub wielokrotnie ważone diagramy Voronoi (lub kombinację powyższych, tj. Można użyć jednego z każdego typu kształtu, tworząc pojedynczy zestaw diagramów od do trzy odrębne klasy obiektów). Jest wciąż w fazie rozwoju, ale powinien być dość stabilny, szczególnie jeśli chcesz robić tylko linie. Dodatek wymaga licencji Spatial Analyst do działania. Sam kod jest open source, więc możesz go dowolnie robić.

https://github.com/UNTGeography/VoronoiDiagramsGIS

Wykorzystuje podobną metodę jak „Alokacja euklidesowa” opisana w odpowiedzi @ radouxju i wykorzystuje raster kierunku przepływu / basenu do tworzenia wielokątów wektorowych z powstałego rastra.

Voronoï jest początkowo przeznaczony do punktów. Oto dwie metody, które mogę sobie wyobrazić dla twojego problemu (powołując się na narzędzia ArcGIS, ale prawdopodobnie możliwe dzięki zgrabnemu):

1)

a) tworzyć punkty wzdłuż linii (np. zagęścić, a następnie obrócić wierzchołki do linii)

b) utwórz wielokąty Thiessena

c) rozpuścić wielokąty Thiessena na podstawie przecinających się linii

2)

a) z analitykiem przestrzennym obliczyć alokację euklidesową do linii

b) przekształcić każdą strefę w wielokąt

Dla niektórych klientów wraz z kilkoma współpracownikami pracowałem nad stworzeniem 2 narzędzi do geoprzetwarzania, które to robią. Chociaż narzędzia geoprzetwarzania nie są publicznie dostępne, użyliśmy pytona i C #:

• Interfejs API C #: https://github.com/fabanc/SharpBoostVoronoi
• Python API: https://github.com/Voxel8/pyvoronoi

Zarówno C #, jak i opakowanie Pythona faktycznie polegają na C ++ Boor Voronoi API: http://www.boost.org/doc/libs/1_54_0/libs/polygon/doc/voronoi_main.htm

Pamiętaj, że interfejs API zużywa dużo pamięci. Nie stanowi to problemu, jeśli korzystasz z Geoprocessing dla wersji 64-bitowej, ArcGIS Pro lub QGIS. Jest to ograniczenie, jeśli korzystasz z ArcGIS Desktop, ponieważ ma on 32 bity. (Szczegółowa sieć dróg o długości 40 000 wierszy lub więcej powinna wystarczyć do osiągnięcia limitu pamięci)

ET Geowizards (wtyczka do Arc) ma do tego narzędzie, które akceptuje polilinie (patrz zrzut ekranu poniżej). Niestety do uruchomienia tego narzędzia potrzebny będzie licencjonowany produkt, ale myślę, że powinien to załatwić sprawę.

Plus jeszcze jeden sposób rozwiązania zadania za pomocą PostgreSQL / PostGIS.

Jeśli linie są krótkie i proste, uruchom skrypt:

WITH
tbla AS (SELECT (ST_Dump(geom)).geom geom FROM <line_name_table>),
tblb AS (SELECT (ST_DumpPoints(geom)).geom geom FROM tbla
        UNION
        SELECT ST_Centroid(geom) geom FROM tbla),
tblc AS (SELECT ((ST_Dump(ST_VoronoiPolygons(ST_Collect(geom)))).geom) geom FROM tblb)
SELECT ST_Union(a.geom) geom FROM tblc a JOIN tbla b ON ST_Intersects(a.geom, b.geom) GROUP BY b.geom;

Zobacz wynik.

Jeśli linie są długie, uruchom skrypt:

WITH
tbla AS (SELECT (ST_Dump(geom)).geom geom FROM <line_name_table>),
tblb AS (WITH btbl AS (SELECT (ST_Dump(geom)).geom geom FROM tbla),
intervals AS (SELECT generate_series (0, 9) as steps)
SELECT steps AS stp, ST_LineInterpolatePoint(geom, steps/(SELECT count(steps)::float-1 FROM intervals)) geom FROM btbl, intervals GROUP BY intervals.steps, geom),
tblc AS (SELECT ((ST_Dump(ST_VoronoiPolygons(ST_Collect(geom)))).geom) geom FROM tblb)
SELECT ST_Union(a.geom) geom FROM tblc a JOIN tbla b ON ST_Intersects(a.geom, b.geom) GROUP BY b.geom;

Zobacz wynik.

Jeśli to konieczne, skompresuj liczbę punktów na liniach, w moim przykładzie jest to 10 punktów.

Oryginalne rozwiązania.

Ten skrypt nazywa się: ST_VoronoiDiagramsFromLines.