Erstellen eines Voronoi-Diagramms in PostGIS

12

Ich versuche von hier aus ein Voronoi-Diagramm aus einem Gitter von Punkten mit modifiziertem Code zu konstruieren . Dies ist eine SQL-Abfrage nach meinen Änderungen:

DROP TABLE IF EXISTS example.voronoi;
WITH 
    -- Sample set of points to work with
    Sample AS (SELECT ST_SetSRID(ST_Union(geom), 0) geom FROM example."MeshPoints2d"),
    -- Build edges and circumscribe points to generate a centroid
    Edges AS (
    SELECT id,
        UNNEST(ARRAY['e1','e2','e3']) EdgeName,
        UNNEST(ARRAY[
            ST_MakeLine(p1,p2) ,
            ST_MakeLine(p2,p3) ,
            ST_MakeLine(p3,p1)]) Edge,
        ST_Centroid(ST_ConvexHull(ST_Union(-- Done this way due to issues I had with LineToCurve
            ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p1,p2),ST_MakeLine(p2,p3)))),'LINE','CIRCULAR'),15),
            ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p2,p3),ST_MakeLine(p3,p1)))),'LINE','CIRCULAR'),15)
        ))) ct      
    FROM    (
        -- Decompose to points
        SELECT id,
            ST_PointN(g,1) p1,
            ST_PointN(g,2) p2,
            ST_PointN(g,3) p3
        FROM    (
            SELECT (gd).Path id, ST_ExteriorRing((gd).geom) g -- ID andmake triangle a linestring
            FROM (SELECT (ST_Dump(ST_DelaunayTriangles(geom))) gd FROM Sample) a -- Get Delaunay Triangles
            )b
        ) c
    )
SELECT ST_SetSRID((ST_Dump(ST_Polygonize(ST_Node(ST_LineMerge(ST_Union(v, ST_ExteriorRing(ST_ConvexHull(v)))))))).geom, 2180)
INTO example.voronoi
FROM (
    SELECT  -- Create voronoi edges and reduce to a multilinestring
        ST_LineMerge(ST_Union(ST_MakeLine(
        x.ct,
        CASE 
        WHEN y.id IS NULL THEN
            CASE WHEN ST_Within(
                x.ct,
                (SELECT ST_ConvexHull(geom) FROM sample)) THEN -- Don't draw lines back towards the original set
                -- Project line out twice the distance from convex hull
                ST_MakePoint(ST_X(x.ct) + ((ST_X(ST_Centroid(x.edge)) - ST_X(x.ct)) * 2),ST_Y(x.ct) + ((ST_Y(ST_Centroid(x.edge)) - ST_Y(x.ct)) * 2))
            END
        ELSE 
            y.ct
        END
        ))) v
    FROM    Edges x 
        LEFT OUTER JOIN -- Self Join based on edges
        Edges y ON x.id <> y.id AND ST_Equals(x.edge,y.edge)
    ) z

Unten - Ergebnis meiner Anfrage. Bildbeschreibung hier eingeben

Wie Sie sehen, erhalte ich ein "fast" korrektes Voronoi-Diagramm, außer hervorgehobenen Punkten, die kein eindeutiges Polygon haben. Nachfolgend sehen Sie, was der QGIS-Algorithmus erzeugt und was ich aus der Abfrage erhalten möchte. Irgendwelche Vorschläge, wo liegt das Problem mit meinem Code?

Bildbeschreibung hier eingeben

DamnBack
quelle
Vielleicht können Sie auch das Ergebnis der SpatiaLite-Funktion "VoronojDiagram" gaia-gis.it/gaia-sins/spatialite-sql-latest.html vergleichen und sich den Quellcode in gaia-gis.it/fossil/libspatialite/ ansehen. Index .
user30184
Gute Frage, ich habe die Frage, auf die Sie sich beziehen, geprüft, um sie zu beschleunigen, aber mir läuft die Zeit davon. Ich war mir dieses Problems mit den äußeren Punkten nicht bewusst.
John Powell
5
Für das, was es wert ist, haben wir ST_Voronoi in PostGIS 2.3, Dan Baston wird bald den Code dafür einchecken - trac.osgeo.org/postgis/ticket/2259 sieht so ziemlich fertig aus, muss nur eingezogen werden. Wäre großartig zu haben Leute testen
LR1234567
Können Sie die von Ihnen verwendeten Punkte zusammenstellen? Es würde mir etwas
ausmachen,
@MickyT Hier ist ein Link zu meinen Daten. Data SRID ist ein 2180.
DamnBack

Antworten:

6

Während dies das unmittelbare Problem mit der Abfrage der fraglichen Daten behebt, bin ich mit dieser Lösung für den allgemeinen Gebrauch nicht zufrieden und werde diese und die vorherige Antwort erneut prüfen, wenn ich kann.

Das Problem bestand darin, dass bei der ursprünglichen Abfrage eine konvexe Hülle an den Voronoi-Kanten verwendet wurde, um die Außenkante für das Voronoi-Polygon zu bestimmen. Dies bedeutete, dass einige der Voronoi-Kanten nicht das Äußere erreichten, als sie hätten sein sollen. Ich habe versucht, die Funktion für den konkaven Rumpf zu verwenden, aber es hat nicht so funktioniert, wie ich es wollte.
Als schnelle Lösung habe ich den konvexen Rumpf so geändert, dass er um den geschlossenen Satz von Voronoi-Kanten sowie einen Puffer um die ursprünglichen Kanten herum erstellt wird. Die Voronoi-Kanten, die sich nicht schließen, werden um eine große Strecke verlängert, um sicherzustellen, dass sie das Äußere schneiden und zum Bilden von Polygonen verwendet werden. Vielleicht möchten Sie mit den Pufferparametern herumspielen.

WITH 
    -- Sample set of points to work with
    Sample AS (SELECT ST_SetSRID(ST_Union(geom), 0) geom FROM MeshPoints2d),
    -- Build edges and circumscribe points to generate a centroid
    Edges AS (
    SELECT id,
        UNNEST(ARRAY['e1','e2','e3']) EdgeName,
        UNNEST(ARRAY[
            ST_MakeLine(p1,p2) ,
            ST_MakeLine(p2,p3) ,
            ST_MakeLine(p3,p1)]) Edge,
        ST_Centroid(ST_ConvexHull(ST_Union(-- Done this way due to issues I had with LineToCurve
            ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p1,p2),ST_MakeLine(p2,p3)))),'LINE','CIRCULAR'),15),
            ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p2,p3),ST_MakeLine(p3,p1)))),'LINE','CIRCULAR'),15)
        ))) ct      
    FROM    (
        -- Decompose to points
        SELECT id,
            ST_PointN(g,1) p1,
            ST_PointN(g,2) p2,
            ST_PointN(g,3) p3
        FROM    (
            SELECT (gd).Path id, ST_ExteriorRing((gd).geom) g -- ID andmake triangle a linestring
            FROM (SELECT (ST_Dump(ST_DelaunayTriangles(geom))) gd FROM Sample) a -- Get Delaunay Triangles
            )b
        ) c
    )
SELECT ST_SetSRID((ST_Dump(ST_Polygonize(ST_Node(ST_LineMerge(ST_Union(v, (SELECT ST_ExteriorRing(ST_ConvexHull(ST_Union(ST_Union(ST_Buffer(edge,20),ct)))) FROM Edges))))))).geom, 2180) geom
INTO voronoi
FROM (
    SELECT  -- Create voronoi edges and reduce to a multilinestring
        ST_LineMerge(ST_Union(ST_MakeLine(
        x.ct,
        CASE 
        WHEN y.id IS NULL THEN
            CASE WHEN ST_Within(
                x.ct,
                (SELECT ST_ConvexHull(geom) FROM sample)) THEN -- Don't draw lines back towards the original set
                -- Project line out twice the distance from convex hull
                ST_MakePoint(ST_X(x.ct) + ((ST_X(ST_Centroid(x.edge)) - ST_X(x.ct)) * 200),ST_Y(x.ct) + ((ST_Y(ST_Centroid(x.edge)) - ST_Y(x.ct)) * 200))
            END
        ELSE 
            y.ct
        END
        ))) v
    FROM    Edges x 
        LEFT OUTER JOIN -- Self Join based on edges
        Edges y ON x.id <> y.id AND ST_Equals(x.edge,y.edge)
    ) z;
MickyT
quelle
Vielen Dank für die Erklärung und schnelle Lösung für das Problem! Es funktioniert mit meinen Daten (etwas langsamer aufgrund von ST_Union(ST_Buffer(geom))), aber ich werde weiterhin mit anderen Punktmengen testen. In der Zwischenzeit werde ich warten, wie Sie sagten - allgemeinere Lösung. :)
DamnBack
Haben Sie ein Bild, das Sie auf Ihrer endgültigen Ausgabe veröffentlichen können?
Jeryl Cook
10

Nach einem Vorschlag von @ LR1234567, die neue ST_Voronoi- Funktionalität, die von @dbaston entwickelt wurde, auszuprobieren, kann die ursprüngliche, erstaunliche Antwort von @MickyT (wie in der Frage von OP angegeben) und die Verwendung der Originaldaten jetzt vereinfacht werden:

WITH voronoi (vor) AS 
     (SELECT ST_Dump(ST_Voronoi(ST_Collect(geom))) FROM meshpoints)
SELECT (vor).path, (vor).geom FROM voronoi;

was zu dieser Ausgabe führt, die mit der Frage des OP identisch ist.

Bildbeschreibung hier eingeben

Dies hat jedoch das gleiche Problem, das jetzt in MickyTs Antwort behoben wurde: Punkte auf der konkaven Hülle erhalten kein umschließendes Polygon (wie vom Algorithmus erwartet). Ich habe dieses Problem mit einer Abfrage mit den folgenden Schritten behoben.

  1. Berechnen Sie die konkave Hülle der Eingabepunkte - Punkte auf der konkaven Hülle sind diejenigen, die im Voronoi-Ausgabediagramm unbegrenzte Polygone haben.
  2. Suchen Sie die ursprünglichen Punkte auf dem konkaven Rumpf (gelbe Punkte in Abbildung 2 unten).
  3. Puffern Sie die konkave Hülle (der Pufferabstand ist willkürlich und könnte aus den eingegebenen Daten möglicherweise optimaler ermittelt werden?).
  4. Suchen Sie die nächstgelegenen Punkte auf dem Puffer der konkaven Hülle, die den Punkten in Schritt 2 am nächsten liegen. Diese werden im folgenden Diagramm als grün angezeigt.
  5. Fügen Sie diese Punkte dem ursprünglichen Datensatz hinzu
  6. Berechnen Sie das Voronoi-Diagramm dieses kombinierten Datensatzes. Wie im 3. Diagramm zu sehen ist, haben die Punkte auf dem Rumpf nun umschließende Polygone.

Abbildung 2 zeigt Punkte auf dem konkaven Rumpf (gelb) und die Punkte, die am nächsten am Rumpf liegen (grün). Diagramm 2.

Die Abfrage könnte natürlich vereinfacht / komprimiert werden, aber ich habe diese Form als eine Reihe von CTEs belassen, da es einfacher ist, die Schritte auf diese Weise sequentiell zu verfolgen. Diese Abfrage wird für den ursprünglichen Datensatz in Millisekunden ausgeführt (Durchschnitt 11 ms auf einem Entwickler-Server), während die Antwort von MickyT mit ST_Delauney in 4800 ms auf demselben Server ausgeführt wird. DBaston behauptet, dass eine weitere Geschwindigkeitsverbesserung in der Größenordnung erzielt werden kann, wenn der aktuelle GEOS-Stamm 3.6dev aufgrund von Verbesserungen in den Triangulationsroutinen verglichen wird.

WITH 
  conv_hull(geom) AS 
        (SELECT ST_Concavehull(ST_Union(geom), 1) FROM meshpoints), 
  edge_points(points) AS 
        (SELECT mp.geom FROM meshpoints mp, conv_hull ch 
        WHERE ST_Touches(ch.geom, mp.geom)), 
  buffered_points(geom) AS
        (SELECT ST_Buffer(geom, 100) as geom FROM conv_hull),
  closest_points(points) AS
        (SELECT 
              ST_Closestpoint(
                   ST_Exteriorring(bp.geom), ep.points) as points,
             ep.points as epoints 
         FROM buffered_points bp, edge_points ep),
  combined_points(points) AS
        (SELECT points FROM closest_points 
        UNION SELECT geom FROM meshpoints),
  voronoi (vor) AS 
       (SELECT 
            ST_Dump(
                  ST_Voronoi(
                    ST_Collect(points))) as geom 
        FROM combined_points)
 SELECT 
     (vor).path[1] as id, 
     (vor).geom 
 FROM voronoi;

Diagramm 3 zeigt alle Punkte, die jetzt in einem Polygon eingeschlossen sind Diagramm 3

Hinweis: Gegenwärtig umfasst ST_Voronoi das Erstellen von Postgis aus der Quelle (Version 2.3 oder Trunk) und das Verknüpfen mit GEOS 3.5 oder höher.

Bearbeiten: Ich habe gerade Postgis 2.3 angeschaut, wie es auf Amazon Web Services installiert ist, und es scheint, dass der Funktionsname jetzt ST_VoronoiPolygons lautet.

Zweifellos könnte diese Abfrage / dieser Algorithmus verbessert werden. Vorschläge sind willkommen.

John Powell
quelle
@dbaston. Sie fragen sich, ob Sie Kommentare zu diesem Ansatz haben?
John Powell
1
na ja, alle Punkte haben einen umschließenden Polygon bekommen, es ist nur , dass es unverhältnismäßig groß ist. Ob und wie diese verkleinert werden sollten, ist ziemlich subjektiv, und ohne genau zu wissen, was für die äußeren Polygone gewünscht wird, ist es schwer zu wissen, was der "beste" Weg ist. Ihre scheint mir eine gute Methode zu sein. Ich habe eine weniger ausgefeilte Methode verwendet, die Ihrer im Geiste ähnlich ist, indem ich zusätzliche Punkte entlang einer gepufferten konvexen Rumpfgrenze in einem festen Abstand abgelegt habe, der durch die durchschnittliche Punktdichte bestimmt wird.
Dbaston
@dbaston. Danke, ich habe nur dafür gesorgt, dass ich nichts Offensichtliches verpasst habe. Ein Algorithmus zum Verkleinern der äußeren Polygone auf etwas, das der Größe der inneren Polygone (in meinem Fall Postleitzahlenbereiche) besser entspricht, ist etwas, worüber ich noch nachdenken muss.
John Powell
@ John Barça Danke für eine weitere großartige Lösung. Die Geschwindigkeit der Berechnungen ist mit diesem Ansatz mehr als zufriedenstellend. Leider möchte ich diesen Algorithmus in meinem QGIS-Plugin verwenden und er muss sofort mit PostGIS 2.1+ funktionieren. Aber ich werde diese Lösung sicherlich nach der offiziellen Veröffentlichung von PostGIS 2.3 verwenden. Trotzdem danke für so umfassende Antworten. :)
DamnBack
@ DamnBack. Du bist herzlich Willkommen. Ich brauchte das für die Arbeit und Ihre Frage hat mir sehr geholfen, da ich keine Ahnung hatte, wie ST_Voronoi herauskommt und die älteren Lösungen viel langsamer sind (wie Sie bemerkt haben). Es hat auch Spaß gemacht, es herauszufinden :-)
John Powell
3

Wenn Sie Zugriff auf PostGIS 2.3 haben, probieren Sie die neue ST_Voronoi-Funktion aus, die kürzlich festgeschrieben wurde:

http://postgis.net/docs/manual-dev/ST_Voronoi.html

Es gibt vorkompilierte Builds für Windows - http://postgis.net/windows_downloads/

LR1234567
quelle
Danke für die Info, dass es eine kommende integrierte ST_Voronoi-Funktion gibt - ich werde es überprüfen. Leider benötige ich eine Lösung, die mit PostGIS 2.1+ -Versionen funktioniert, sodass die @ MickyT-Abfrage derzeit meinen Anforderungen am nächsten kommt.
DamnBack
@ LR1234567. Benötigt dies eine bestimmte Version von GEOS? Ich habe morgen Zeit, 2.3 und ST_Voronoi zu testen.
John Powell
Benötigt GEOS 3.5
LR1234567