Erstellen Sie ein Mosaik wie ein Voronoi-Diagramm aus disjunkten Polygonen

12

Die folgende Abbildung zeigt das Problem :

Bildbeschreibung hier eingeben

Wie in (a) habe ich eine Reihe von disjunkten Polygonen als Geometrien in PostGIS. Ich brauche so etwas wie (b) , das "Mosaik" dieses Satzes von Polygonen, das nach einem "Einflussbereich" -Kriterium erstellt wird ... Ist wie eine Voronoi-Konstruktion (dargestellt durch (c) ): in der Tat, wenn die Polygone waren Punkte sind die Einflussregionen Voronoi.

Zusammenfassend: Ich benötige einen SQL-Algorithmus (oder einen speziellen für PostGIS), der das "Mosaik" einer Menge von disjunkten Polygonen erzeugt. (Vielleicht eine Schleife mit kleinen ST_Buffer- und ST_Difference-Operationen)

PS: Ich brauche, wie Voronos, dass die Raumbegrenzung (ein quadratischer Rahmen in (b) ) ignoriert wird.


Dieses Problem ähnelt dem anderen in Bezug auf Linien .

EDIT (nach @FelixIP Kommentar)

Ich preffer bleiben Vektor Universum, nicht verloren Präzision (ex. Mit ST_DelaunayTriangles und Addieren und Subtrahieren Innenräume durch die ursprünglichen Polygone, so dass sie eine Anpassung der dualen Graphen Lösung ) ... Einige einfache und automatische Pakete wie pprepair (unterstützt wie QGIS topologischen Werkzeuge sind nicht automatisch). Aber Raster ist vielleicht einfacher und verbraucht weniger CPU.

Diese "GRID-Prozess" -Darstellung ist auch als Lösung gültig, vorausgesetzt, dass sie die gleiche Präzision und das "Wachstum der euklidischen Einflussregion" ermöglicht.

Bildbeschreibung hier eingeben

In ARCGIS gibt es ein räumliches Analyse-Tool, das als Euklidische Allokation bezeichnet wird. Daher gibt es möglicherweise eine PostGIS-ähnliche Lösung , die mit der Menge der Polygone beginnt (Klassifizieren, Rastern und Zurücksetzen der Polygone).

Peter Krauss
quelle
Danke @Nir, entschuldigen Sie die Verwechslung mit Punkten, ich verwende keine Punkte, nur Polygone als Elemente (a) und (b) der Abbildung ... Haben Sie einen Link zu Ihrer Lösung?
Peter Krauss
In arcgis gibt es eine Rasterlösung namens eukledische Zuordnung oder Nähe
FelixIP
Danke @FelixIP, ich habe bearbeitet, um "gut Raster-Lösungen zu kommen" ;-)
Peter Krauss
Wenn Sie Ihre Polygone aus ihrer Ausdehnung löschen. Das Grundgerüst dafür ist, denke ich, gis.stackexchange.com/questions/177/… . Die Implementierung ist ein Riesenerfolg
FelixIP
1
@ Cyril, ich kann Ihre Skripte überprüfen ... Nächste Woche. Ein guter erster Schritt ist, etwas zu posten, das mit modernen PostGIS-Funktionen eine Lösung zu sein scheint.
Peter Krauss

Antworten:

1

Wenn ich die Frage richtig verstanden habe und wie bereits erwähnt, trägt ihr Kreativteam die Verantwortung für den Betrieb des PostGIS-Ofens.

Ich werde darum bitten, mich von niemandem in meinem humorvollen Stil beleidigen zu lassen und es als Spiel zu verstehen!

Die Originaldatei besteht aus geschnittenen Früchten und einfachen Formen (im Folgenden als Frucht bezeichnet), siehe Abbildung 1 unten.

Bildbeschreibung hier eingeben

Hier ist mein Rezept und ich werde dabei von lieben Programmierern unterstützt, die Sie später kennenlernen werden. Beginnen wir, und dafür werden wir einen Teig herstellen, in den unsere Früchte gelegt werden, für den das Skript ausgeführt wird:

create table poly_extent as SELECT ST_SetSRID(ST_Buffer(ST_Envelope(ST_Extent(geom)),0.05),4326) as geom FROM poly;

Siehe das Ergebnis in Abbildung 2 unten

Bildbeschreibung hier eingeben

Wenn es nur wenige Früchte gibt, wie in meinem Bild, erstellen Sie den Rand des externen Puffers auf der Frucht, oder wenn es viele Früchte gibt, erstellen Sie den Rand des negativen Puffers, für den das Skript ausgeführt wird:

create table poly_buff_dump as SELECT ((ST_Dump(ST_Boundary(ST_Union(ST_Buffer((geom),0.01, 'join=mitre mitre_limit=5.0'))))).geom) geom FROM poly;

Und schneiden Sie die Pufferlinien um jede Frucht

UPDATE poly_buff_dump SET geom=ST_RemovePoint(geom, ST_NPoints(geom)-1) WHERE ST_IsClosed(geom)=true; Siehe das Ergebnis in Abbildung 3 unten

Bildbeschreibung hier eingeben

(Eigentlich dachte ich, dass ich als Ergebnis unterbrochene Linien bekommen würde (wie in einem Kreis), aber wenn die Figuren schwierig sind, werden manchmal Brüche erhalten, falsche, zum Beispiel eine Seite des Rechtecks ​​fiel ab usw. )

Dann müssen Sie die erhaltenen Linien auf eine für Sie bequeme Weise in gleiche Segmente unterteilen und Punkte daraus extrahieren

create table poly_buff_dump_pt as SELECT (ST_DumpPoints((geom))).geom geom FROM poly_buff_segm;

Ergebnis, siehe Abbildung 4 unten

Bildbeschreibung hier eingeben

Führen Sie nun das Voronoi-Tool aus. An dieser Stelle habe ich das von MickyT vorgeschlagene Tool verwendet: /gis//a/172246/120129 , wodurch Sie Tabellen mit dem Namen „voronoi“ erstellt haben "Für die Tatsache, dass" mein erster Assistent "vom Küchenchef getrennt ist, danke vom Küchenchef!" :-).

Die zweite Möglichkeit in diesem Schritt besteht darin, die Funktion ST_VoronoiPolygons auszuführen.

Ergebnis, siehe Abbildung 5 unten

Bildbeschreibung hier eingeben

Schneiden Sie nun die zusätzlichen Teile aus, indem Sie das Skript ausführen:

create table poly_voronoi_cut as SELECT ST_Intersection(a.geom, b.geom) geom FROM voronoi a INNER JOIN poly_extent b ON ST_Intersects(a.geom, b.geom); Ergebnis, siehe Abbildung 6 unten.

Bildbeschreibung hier eingeben

Führen Sie nun das Skript aus, um den Geodatentyp in LineString auszurichten:

create table poly_voronoi_dump as SELECT (ST_Dump(geom)).geom as geom FROM poly_voronoi_cut; Und jetzt werde ich "meinen zweiten Kumpel" bitten, meine Pflichten zu übernehmen und den Kuchen zu mixen (Jeff - /gis//a/785/120129 ), und zwar in einer einzigen Schicht und dafür , danke mir dafür!

CREATE TABLE poly_overlay_cut AS SELECT geom FROM ST_Dump(( SELECT ST_Polygonize(geom) AS geom FROM ( SELECT ST_Union(geom) AS geom FROM ( SELECT ST_ExteriorRing(geom) AS geom FROM poly_voronoi_dump) AS lines ) AS noded_lines ) ); Jetzt ist es Zeit für mich, mich an die Arbeit zu machen, für die ich das Skript ausführe:

create table poly_voronoi_union as SELECT b.id, (ST_ConvexHull(ST_Union(a.geom, b.geom))) geom FROM poly_overlay_cut a INNER JOIN poly_buff_dump b ON ST_Intersects(a.geom, b.geom) GROUP BY b.id, a.geom, b.geom; und ein weiteres Skript:

create table poly_voronoi_union_area as SELECT ST_Union(ST_ConvexHull(ST_BuildArea(geom))) as geom FROM poly_voronoi_union GROUP BY id; siehe Abbildung 7 unten

Bildbeschreibung hier eingeben

Wie Sie auf dem Bild sehen können, haben unsere Schnitte kleine Ebenen, die optional mit ST_SnapToGrid (oder auf andere Weise) entfernt werden können:

Und zum Schluss werden wir unsere gebackenen Früchte aus unserer Torte herausschneiden, ich bin sogar ein bisschen müde geworden, als ich am Ofen stand :-)

create table polygon_voronoi_result as SELECT (ST_Dump(ST_Difference(a.geom, b.geom))).geom as geom FROM poly_voronoi_union_area_snap as a JOIN poly b ON ST_Intersects(a.geom, b.geom); Ergebnis siehe Abbildung 8 Bildbeschreibung hier eingeben

Alles von diesem Tag an wird jetzt jeder lernen, leckere Kuchen zu backen - Obstteller. Hilf dir selbst, und wähle die Teile aus, die dir gefallen, genug für alle.

(Es ist schade, dass ich wirklich nicht alle Menschen ernähren kann, nicht mit elektronischen Kuchen, sondern mit echten Kuchen, vielleicht würde der Hunger auf der Erde enden ...)

Edit: Die Kirsche auf dem Kuchen könnte so aussehen :-):

WITH
tbla AS (SELECT (ST_DumpPoints(geom)).geom geom FROM poly),
tblb AS (SELECT ((ST_Dump(ST_VoronoiPolygons(ST_Collect(geom)))).geom) geom FROM tbla),
tblc AS (SELECT ST_Intersection(a.geom, b.geom) geom FROM tblb a JOIN poly_extent b ON ST_Intersects(a.geom,b.geom)),
tbld AS (SELECT id, ((ST_Dump(geom)).geom) geom FROM poly GROUP BY id, geom)
SELECT id, ST_Union(a.geom) as geom FROM tblc a JOIN tbld b ON ST_Intersects(a.geom, b.geom) GROUP BY id;

oder

WITH
tbla AS (SELECT (ST_DumpPoints(geom)).geom geom FROM polygons),
tblb AS (SELECT ((ST_Dump(ST_VoronoiPolygons(ST_Collect(geom)))).geom) geom FROM tbla),
tblc AS (SELECT id, ((ST_Dump(geom)).geom) geom FROM polygons GROUP BY id, geom)
SELECT id, ST_Union(a.geom) geom FROM tblb a JOIN tblc b ON ST_Intersects(a.geom, b.geom) GROUP BY id;

Mit dir war gut und fair Mr.Baker, vielen Dank und viel Glück, :-) ...

Originelle Lösungen.

Dieses Skript heißt: ST_VoronoiDiagramsFromPolygons.

Cyril M
quelle
1
Hallo, gute Illustrationen und scheinbar gutes Ergebnis (!). Vorschlag zu einer kurzen Diskussion, siehe @geogeek Lösung, die Schritte in QGis scheinen hier die Hauptschritte von PostGIS zu sein ... Warum brauchen wir ST_Bufferund ST_ConvexHull? Gibt es einen alternativen Algorithmus?
Peter Krauss
1) Siehe, ST_Buffer und on-Polygone werden erstellt, um die Trennlinien zwischen den Originalfiguren während der Anwendung der Voronoi-Funktion zu verringern. Je größer der Puffer, desto gleichmäßiger werden die Trennlinien erstellt eine Voronoi-Funktion ... 2) ST_ConvexHull aus der Vielzahl der Figuren auf jedem Polygon, das Polygon, das wir brauchen ... 3) Heute ist dies meine Vision, Ihre Frage zu lösen, ich weiß nicht, was mit uns allen passieren wird und unsere Entscheidungen in der Zukunft ...
Cyril M
Ein weiterer wichtiger Wert der Pufferlinien ist, dass sie uns helfen, Fragmente aus dem Ergebnis der Funktion der Voronoi auszuwählen, um kombinierte Polygone für jede Form zu erstellen ...
Cyril M
Übrigens begrüße ich die Verbesserung des Codes und Ansatzes, damit sie das Ergebnis nicht verschlechtern ...
Cyril M
1
Hallo Cyril, ich stimme zu, dass ST_Buffer eine gute Option ist, um die Konturlinien zu normalisieren, perfekt (!). Über ST_ConvexHull, ist nur eine Kuriosität, welche Art von Ergebnissen wir nach Abbildung 6 poly_voronoi_unionerzielen können, ohne ST_ConvexHull.
Peter Krauss
8

Postgis haben keine dedizierte Funktion für voronoi, aber Qgis enthält eine vornoi-Funktion, mit der aus Punkten voronoi-Polygone erstellt werden können. Mit qgis habe ich die folgenden Schritte ausgeführt, um diese Ergebnisse zu erzielen:

- Erstelle Punkte aus Polygonen mit extract nodesFunktionen.

-Erstelle Vornoi-Polygone mit Voroi-Funktionen in Qgis.

-Erstelle einen räumlichen Join in Qgis.

Ergebnisse auflösen.

Bildbeschreibung hier eingeben

Geogeek
quelle
1
Schöne Lösung (!) Und danke der Illustration. Kannst du es verbessern? Siehe das linke Rechteck unten, es waren 4 Punkte bei Voronoi, und die Mitte des Rechtecks ​​hat keine Repräsentation, verzerrt seinen Bereich (die Verluste gehen auf das Dreieck zurück) ... Vielleicht ist eine Verbesserung möglich, indem regelmäßig von jedem Polygon eine Abtastung durchgeführt wird ... und vielleicht auch ein paar innere punkte.
Peter Krauss
Ich verwende das Verdichtungswerkzeug in ArcGIS. Dies verbessert die Nachbarschaftspolygone erheblich. +1
FelixIP
3

OK - Ich habe ein wenig darüber nachgedacht und festgestellt, dass es etwas ist, was ich mir in letzter Zeit angesehen habe.

Nimm deine Start-Polys:

Bildbeschreibung hier eingeben

Generieren Sie ein neues Attribut mit einer Zahl (in meinem Fall 100). Verwenden Sie das Werkzeug Vektor-> Recherchieren -> Zufällige Punkte innerhalb von Polygonen. Dadurch werden (100) Punkte innerhalb jedes Polygons generiert: Bildbeschreibung hier eingeben

Dann Vektor-> Geometriewerkzeuge -> Voronoi, um Polys basierend auf dieser Punktebene zu generieren.

Bildbeschreibung hier eingeben

Jetzt können Sie das Werkzeug Vektor -> räumliche Abfrage verwenden: Wählen Sie die Punkte aus, die zu einem Polygon (oder einem der Polygone) gehören. Verwenden Sie das Werkzeug für räumliche Abfragen, um eine Auswahl Ihrer Voronoi-Polygone zu generieren, die für dieses Polygon gelten. Fügen Sie dem Voroni-Polygon ein Attribut hinzu, das dem gewünschten Polygon entspricht. (Ich habe gerade 1,2,3,4 verwendet)

Jetzt können Sie Vektor-> Geoverarbeitungswerkzeuge-> basierend auf Ihrem neuen Attribut auflösen.

Bildbeschreibung hier eingeben

AA
quelle
Danke @AAmes (!), Die Abbildungen sind gut und die Methode ist eine gute Alternative ... Aber die Frage betrifft "einen SQL-Algorithmus (oder einen bestimmten für PostGIS)" und jetzt die Prämie für die Verwendung der Funktion ST_VoronoiPolygons () , die vielleicht alle Probleme mit einem Klick lösen ;-)
Peter Krauss
@AAmes Eine schnelle Suche zeigt, dass diese Methode auch in PostGIS verwendet werden kann. Wie Sie in postgis zufällige Punkte in einem Polygon erstellen, erklärt die Punkterstellung aus Polygonen und von dort aus sollte es ziemlich einfach sein.
Phil G
Mein Kopfgeld galt Ihnen als Ansporn (willkommen hier!), Aber DIESE ANTWORT ENTSPRICHT den Fragen und Kopfgeldanforderungen.
Peter Krauss
Danke Peter, ich habe deine Notizen gesehen, aber leider hatte ich nicht die Gelegenheit, zurückzukommen und sie anzusprechen. Ich habe noch keine Erfahrung mit PostGIS und es hätte mehr Zeit gekostet, als mir zur Verfügung stand, um eine gute Antwort zu geben. Ich hoffe, dass unsere Erkundung dieses Raumes den Menschen in Zukunft hilfreich sein wird. Wenn ich bald einen Sprung bei PostGIS bekomme, werde ich wiederkommen und einen weiteren Schlag darauf machen, um zu üben!
AA
2

Zufällige Punkte sind eine gute Idee, um ein Voronoi-Polygon aus Polygonen zu generieren. Es funktioniert ziemlich gut, aber für Polygone, die nahe beieinander liegen, ist es ziemlich schlecht: Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

ST_ApproximateMedialAxis ist eine weitere gute Alternative, wenn PostGIS verwendet wird: Berechnung von Voronoi-Diagrammen für Polygone

Löwe
quelle