Budowanie wielokąta na dostępnym obszarze

Obecnie pracuję w dziedzinie izochron i podstawowych algorytmów. To, co teraz powoduje problemy, to nie obliczenie samego izochronu, ale wizualizacja wyników.
Wynikiem mojego algorytmu izochronicznego są punkty i krawędzie. W rzeczywistości mam działające rozwiązanie, ale dla 3873 krawędzi i 1529 węzłów wszystko wydaje się trwać wiecznie (około 2,0 sekundy na moim laptopie Lenovo T440s, który zawiera procesor Core i7 2015 i dość szybki dysk SSD). Zamiast sekund chcę coś więcej jak msec :-).

Może ktoś może mi pomóc w skróceniu czasu obliczeń potrzebnego do zbudowania wielokątów, które wizualizują dostępne obszary.

Ale poczekaj ... najpierw najważniejsze!
Oto wizualizacja krawędzi, które są wynikiem obliczeń mojego izochronu: Te krawędzie są przechowywane w tabeli bazy danych PostGIS i są prostymi liniami.

To, co chcę pokazać użytkownikowi, wygląda następująco: Zwróć uwagę na odłączone obszary na południu i na wschód od obrazu. Powinny być one narysowane jako osobne obszary (więc scalanie nie jest tutaj dozwolone :-))

Obecnie używam tego zapytania:

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_MakePolygon(ST_ExteriorRing(ST_GeometryN(segments, generate_series(1, ST_NumGeometries(segments))))) AS polygons FROM (
        SELECT ST_Union(ST_Buffer("GEOMETRY", 20, 'quad_segs=2')) AS segments FROM my_edges AS a
    ) AS b
) AS c

Przeprowadziłem już eksperymenty i przeczytałem dużo dokumentacji, ale po prostu nie mogę znaleźć lepszego rozwiązania.
Moim zdaniem dużym problemem jest użycie ST_Union (jak stwierdzono w dokumentacji, ta funkcja może być powolna). Bardzo interesujące jest to, że zastąpienie go ST_Collect wydaje się spowalniać obliczanie ST_Buffer, dzięki czemu poniższe zapytanie trwa jeszcze dłużej, chociaż nie wypełnia obszarów między krawędziami (tworzy tylko bufor wokół linii ):

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_Buffer(ST_Collect(ST_LineMerge("GEOMETRY")), 20, 'quad_segs=2') AS polygons FROM my_edges AS a
) AS b

W moim systemie zajmuje to około 3,8 sekundy (prawie dwa razy więcej). Mój pierwszy wniosek z tego małego testu porównawczego jest taki, że ST_Buffer staje się nieoczekiwanie powolny, jeśli chodzi o MultiLineStrings (nawet wolniej niż podczas tworzenia buforów dla każdej linii i łączenia buforów - co moim zdaniem jest po prostu dziwne)

Próbowałem także użyć kształtów alfa (używając implementacji z pgRouting), ale ponieważ nie ma żadnej wartości alfa do ustawienia (a tak naprawdę nie chciałbym teraz, do której wartości ustawić taką wartość), po prostu otrzymuję jeden wielki wielokąt ( więc straciłbym regiony na południu i wschodzie jako osobne regiony, co nie jest tym, czego chcę).
Również ST_Polygonize (co było pierwszą rzeczą, jaka przyszła mi do głowy) nie przyniosło żadnych użytecznych rezultatów, ale być może coś mi umknęło ...

Czy istnieje lepszy sposób na utworzenie obszaru pokazanego w PostGIS? Może także przy użyciu kodu java (jts) lub kodu javascript po stronie klienta (jsts)? W rzeczywistości mógłbym żyć z utratą pewnych szczegółów, o ile obszary pokazane w moim wyniku pozostaną rozdzielone, a obliczenia będą (znacznie) szybsze.

Pomijając serializację GeoJSON, na moim laptopie trwa około 6,3 sekundy:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(geom, 20, 2)))).geom))
FROM bz_edges

Patrząc na dane w OpenJUMP, zauważyłem sporo szczegółów w segmentach ulic w stosunku do pożądanego poziomu szczegółowości na wyjściu. Wydaje się, że nawet uproszczenie tych linii w locie może spowodować duże przyspieszenie w PostGIS:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(ST_Simplify(geom, 10), 20, 2)))).geom))
FROM bz_edges

co sprowadza rzeczy do 2,3 sekundy. Pomyślałem, że mógłbym zrobić lepiej, przechowując uogólnioną geometrię w osobnej kolumnie zamiast obliczać ją w locie, ale tak naprawdę nie przyniosło to żadnych dodatkowych korzyści.

W zależności od tego, ile kodu chcesz napisać, prawie na pewno możesz zrobić lepiej w Javie, jeśli nic więcej, ponieważ możesz skorzystać z wielu rdzeni. (Za ile jest warte, JTS wykonuje powyższą operację w 2,8 sekundy). Jednym z podejść może być rozszerzenie, CascadedPolygonUnionaby niektóre operacje związkowe odbywały się równolegle. (aktualizacja - tutaj jest ParallelCascadedPolygonUnion )

Zauważyłem w przykładowych danych, że krawędzie są przechowywane wraz z odniesieniami do ich początkowych i końcowych węzłów, tj. Masz wcześniej zbudowany wykres. Podejrzewam, że możesz generować te wielokąty znacznie szybciej, jeśli pracujesz na wykresie zamiast używać ogólnych operacji geometrii. Na przykład myślę, że można by coś takiego:

1. zidentyfikować połączone elementy wykresu
2. dla każdego podłączonego komponentu znajdź węzeł o minimalnej współrzędnej X (z pewnością na zewnątrz komponentu)
3. przejdź po krawędziach komponentu, zawsze skręcając w lewo (lub w prawo), jeśli to możliwe. To da ci zewnętrzny pierścień każdego elementu.
4. odpowiednio poligonizować zewnętrzny pierścień i bufor.