Erstellen eines Polygons über einem erreichbaren Bereich

10

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: Isochronenberechnungsergebnis (Skelett vorhanden von Linestrings) Diese Kanten werden in einer PostGIS-Datenbanktabelle gespeichert und sind einfache Linestrings.

Was ich dem Benutzer zeigen möchte, sieht folgendermaßen aus: Geben Sie hier die Bildbeschreibung ein 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.

Nikolaus Krismer
quelle
Können Sie nicht einfach ST_Exteriorring (ST_Dump (ST_Union (ST_Buffer (geom, ....))) verwenden? Möglicherweise müssen Sie nach einem Puffer auf Linestrings testen, die manchmal aus ST_Union resultieren. Mit ST_GeometryType (geom) ist dies jedoch einfach. Wenn Sie Java oder jsts verwenden, können Sie dies, aber es ist unwahrscheinlich, dass es schneller ist, da a Ein großer Teil der Postgis (GEOS) -Funktionen sind in erster Linie C / C ++ - Ports von JTS.
John Powell
Sie haben Recht, das funktioniert, aber tatsächlich ist es nicht schneller (dauert ~ 3,1 Sekunden, während die Verwendung von GeometryN 2 Sekunden dauert). Folgendes habe ich verwendet: SELECT ST_AsGeoJson (ST_Transform (ST_Exteriorring ((ST_Dump (ST_Union (ST_Buffer ("GEOMETRY", 20))). Geom), 4326)) FROM my_edges;
Nikolaus Krismer
@ john-barça: Oh .. Ich beschlage den Teil quad_segs = 2 im ST_Buffer, wenn ich Ihren Ansatz versuche ... mit dieser Änderung sind die Abfragen gerade (beide bei ungefähr 2 Sekunden). Dies ist jedoch immer noch sehr langsam (in meinen Augen). Gibt es eine andere Möglichkeit, es zu versuchen?
Nikolaus Krismer
Interessantes Problem .... möchten Sie einige Testdaten teilen?
Dbaston
Wenn es hilft, teile ich gerne einige Daten. Alle Dinge, die ich hier mache, sind Open Source, daher sollte dies kein großes Problem sein. Als erstes ist zu beachten: Eine Webanwendung zum Testen befindet sich unter dbis-isochrone.uibk.ac.at:8080/testing . Weitere Informationen zu den Dingen, an denen ich arbeite, finden Sie unter dbis-isochrone.uibk.ac.at . Im Abschnitt "Links" der Website gibt es einige weitere Referenzen (einschließlich einiger Testdaten)
Nikolaus Krismer

Antworten:

5

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.
dbaston
quelle
Danke ... Vereinfachung ist eine großartige und sogar "einfache" Verbesserung. Die auf meinem Laptop benötigte Zeit dauerte bis zu 1,5 Sekunden. Es ist nicht dort, wo ich sein möchte, aber ein bisschen besser.
Nikolaus Krismer
Bezüglich Ihrer vorgeschlagenen Lösung (Punkte 1-4). Klingt auch sehr einfach und ist einen Versuch wert. Ich dachte an etwas Ähnliches, aber ich stecke bei Punkt 1 fest (also sehr früh :-)). Wie würde man verbundene Komponenten identifizieren (ich kann mir nur eine rekursive Abfrage vorstellen, die auch sehr langsam sein kann).
Nikolaus Krismer
@NikolausKrismer Ich benutze sowohl JGraphT als auch Webstuhl für Aufgaben wie diese. Wenn Sie stattdessen Ihre eigenen Diagrammmethoden schreiben (keine schlechte Idee für die beste Leistung), werden Sie bei einer Tiefensuche nach den Komponenten gesucht. (Sie könnten sie im kommenden PostGIS 2.2 mit finden, ST_ClusterIntersectingaber ich denke, Sie möchten, dass jede Art von Grafikverarbeitung sowieso außerhalb der Datenbank stattfindet, daher ist dies wahrscheinlich nicht nützlich.)
Dbaston
Dies sind einige gute Hinweise. Ich habe mir JGraphT angesehen und dies könnte sicherlich helfen, mein Problem zu lösen. Ich habe mir jedoch auch Postgis 2.2 und die ST_ClusterIntersecting-Funktion angesehen -> es dauert ungefähr 200-250 ms, um die verschiedenen Cluster im obigen Fall zu identifizieren. Das ist in Ordnung für mich (JGraphT könnte es sicherlich besser machen). Jetzt muss ich mich mit dem Erstellen des externalRing befassen (ST_ExteriorRing schlägt fehl, da ST_MakePolygon sagt, dass meine Links keine Shell sind)
Nikolaus Krismer
Ich sehe zwei Komplikationen: (a) Sie benötigen nicht nur den Außenring, sondern auch alle Segmente, die sich von diesem Ring nach außen erstrecken, und (b) es sieht so aus, als würden sich Ihre Linien an einigen Kreuzungen nicht wirklich schneiden. Sie müssen (b) korrigieren, wenn Sie versuchen möchten, eine Geometrie aus den Ergebnissen eines Diagrammspaziergangs zu erstellen.
Dbaston