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)
) zUnten - Ergebnis meiner Anfrage.
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?
postgis
sql
voronoi-thiessen
DamnBack
quelle
quelle
Antworten:
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.
quelle
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. :)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:
was zu dieser Ausgabe führt, die mit der Frage des OP identisch ist.
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.
Abbildung 2 zeigt Punkte auf dem konkaven Rumpf (gelb) und die Punkte, die am nächsten am Rumpf liegen (grün).
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.
Diagramm 3 zeigt alle Punkte, die jetzt in einem Polygon eingeschlossen sind
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.
quelle
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/
quelle