Erstellen eines Polygons über einem erreichbaren Bereich

Ich arbeite derzeit auf dem Gebiet der Isochronen und der zugrunde liegenden Algorithmen. Was nun Probleme verursacht, ist nicht die Berechnung der Isochron selbst, sondern die Visualisierung der Ergebnisse.
Das Ergebnis meines Isochronenalgorithmus sind Punkte und Kanten. Tatsächlich habe ich eine funktionierende Lösung, aber für 3873 Kanten und 1529 Knoten scheinen die Dinge ewig zu dauern (ungefähr 2,0 Sekunden auf meinem Lenovo T440s-Laptop, der eine 2015 Core i7-CPU und eine ziemlich schnelle SSD enthält). Anstelle von Sekunden möchte ich etwas mehr wie ms :-).

Vielleicht kann mir jemand helfen, die Rechenzeit zu verkürzen, die zum Erstellen der Polygone benötigt wird, die die erreichbaren Bereiche visualisieren.

Aber warte ... das Wichtigste zuerst!
Hier ist eine Visualisierung der Kanten, die das Berechnungsergebnis meiner Isochron sind: Diese Kanten werden in einer PostGIS-Datenbanktabelle gespeichert und sind einfache Linestrings.

Was ich dem Benutzer zeigen möchte, sieht folgendermaßen aus: Beachten Sie die getrennten Bereiche ganz im Süden und ganz östlich des Bildes. Diese sollten als separate Bereiche gezeichnet werden (hier ist also kein Zusammenführen erlaubt :-))

Derzeit verwende ich diese Abfrage:

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

Ich habe bereits experimentiert und viel Dokumentation gelesen, aber ich kann einfach keine bessere Lösung finden.
In meinen Augen ist das große Problem die Verwendung von ST_Union (wie in den Dokumenten angegeben, kann diese Funktion langsam sein). Das sehr Interessante ist, dass das Ersetzen durch ST_Collect die ST_Buffer-Berechnung zu verlangsamen scheint, sodass die folgende Abfrage insgesamt noch länger dauert, obwohl sie die Bereiche zwischen den Kanten nicht ausfüllt (es wird nur ein Puffer um die Linien erstellt ):

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

Dies dauert auf meinem System ungefähr 3,8 Sekunden (also fast doppelt so lange). Meine erste Schlussfolgerung aus diesem kleinen Benchmark ist, dass ST_Buffer bei MultiLineStrings unerwartet langsam wird (sogar langsamer als beim Erstellen von Puffern für jede Zeile und beim Zusammenführen der Puffer - was in meinen Augen einfach komisch ist).

Ich habe auch versucht, Alpha-Formen zu verwenden (unter Verwendung der Implementierung von pgRouting), aber da kein Alpha-Wert festgelegt werden muss (und tatsächlich würde ich jetzt nicht wirklich wissen, auf welchen Wert ein solcher Wert festgelegt werden soll), erhalte ich nur ein großartiges Polygon ( Ich würde also die Regionen im Süden und Osten als separate Regionen verlieren, was nicht das ist, was ich will.
Auch ST_Polygonize (was mir als erstes in den Sinn kam) brachte keine brauchbaren Ergebnisse, aber vielleicht habe ich hier etwas verpasst ...

Gibt es eine bessere Möglichkeit, den in PostGIS angezeigten Bereich zu erstellen? Vielleicht auch mit Java-Code (jts) oder clientseitigem Javascript-Code (jsts)? Tatsächlich könnte ich damit leben, einige Details zu verlieren, solange die in meinem Ergebnis gezeigten Bereiche getrennt bleiben und die Berechnung (viel) schneller wird.

Abgesehen von der GeoJSON-Serialisierung dauert Folgendes auf meinem Laptop ungefähr 6,3 Sekunden:

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

Als ich mir die Daten in OpenJUMP ansah, bemerkte ich einige Details in den Straßensegmenten, bezogen auf den gewünschten Detaillierungsgrad in der Ausgabe. Es scheint, dass selbst eine sofortige Vereinfachung dieser Leitungen zu einer großen Beschleunigung von PostGIS führen kann:

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

Das bringt die Dinge auf 2,3 Sekunden. Ich dachte, ich könnte es vielleicht besser machen, wenn ich die verallgemeinerte Geometrie in einer separaten Spalte speichere, anstatt sie im laufenden Betrieb zu berechnen, aber das brachte tatsächlich keinen zusätzlichen Vorteil.

Je nachdem, wie viel Code Sie schreiben möchten, können Sie in Java mit ziemlicher Sicherheit bessere Ergebnisse erzielen, nicht zuletzt, weil Sie mehrere Kerne nutzen können. (Für das, was es wert ist, führt JTS den obigen Vorgang in 2,8 Sekunden durch). Ein Ansatz könnte CascadedPolygonUniondarin bestehen, einige der Gewerkschaftsoperationen parallel durchzuführen. (Update - hier ist eine ParallelCascadedPolygonUnion )

Ich habe in den Beispieldaten festgestellt, dass die Kanten mit Verweisen auf ihre Start- und Endknoten gespeichert sind, dh Sie haben ein vorgefertigtes Diagramm. Ich vermute, Sie können diese Polygone viel schneller generieren, wenn Sie aus dem Diagramm heraus arbeiten, anstatt generische Geometrieoperationen zu verwenden. Zum Beispiel denke ich, Sie könnten so etwas wie das:

1. Identifizieren Sie die verbundenen Komponenten des Diagramms
2. Suchen Sie für jede verbundene Komponente den Knoten mit der minimalen X-Koordinate (die sich garantiert außerhalb der Komponente befindet).
3. Gehen Sie über die Kanten des Bauteils und drehen Sie sich nach Möglichkeit immer nach links (oder rechts). Dadurch erhalten Sie den Außenring jeder Komponente.
4. Polygonisieren Sie den Außenring und puffern Sie ihn entsprechend.