Créez une mosaïque comme le diagramme de Voronoi à partir de polygones disjoints

12

L'illustration ci-dessous montre le problème :

entrez la description de l'image ici

comme dans (a) j'ai un ensemble de polygones disjoints, comme des géométries dans PostGIS. J'ai besoin de quelque chose comme (b) , la "mosaïque" de cet ensemble de polygones, en le construisant selon un critère de "région d'influence" ... C'est comme une construction de Voronoi (illustrée par (c) ): en fait, si les polygones étaient points, les régions d'influence sont Voronoi.

En résumé: j'ai besoin d'un algorithme SQL (ou d' un algorithme spécifique à PostGIS) qui génère la "mosaïque" d'un ensemble de polygones disjoints. (peut-être une boucle de petites opérations ST_Buffer et ST_Difference)

PS: J'ai besoin, comme Voronoi, que la délimitation de l'espace (un cadre carré en (b) ) soit ignorée.


Ce problème est similaire à cet autre sur les lignes .

EDIT (après le commentaire @FelixIP)

Je préfère rester dans l' univers vectoriel , pour ne pas perdre de précision (ex. En utilisant ST_DelaunayTriangles et en ajoutant et en soustrayant des intérieurs par les polygones originaux, en adaptant une solution à double graphique ) ... Quelques packages simples et automatiques comme pprepair (assisté comme les outils topologiques QGIS ne sont pas automatiques). Mais le raster est peut-être plus simple et moins consommateur d'UC.

Cette illustration du "processus GRID" est également valable comme solution, en supposant qu'elle peut permettre la même précision et une "région d'influence euclidienne croissante".

entrez la description de l'image ici

En ARCGIS existe un outil d'analyse spatiale connue sous le nom allocation euclidienne , donc, peut - être il y a une PostGIS solution similaire , en commençant par l'ensemble des polygones (classification, pixelliser et making-retour des polygones).

Peter Krauss
la source
Merci @Nir, désolé la confusion avec les points, je n'utilise pas de points, seulement des polygones comme éléments (a) et (b) de l'illustration ... Avez-vous un lien de votre indice sur la solution?
Peter Krauss
Dans arcgis, il existe une solution raster appelée allocation euclédienne ou proximité
FelixIP
Merci @FelixIP, j'ai édité pour "bien venir des solutions raster" ;-)
Peter Krauss
Si vous supprimez vos polygones de leur étendue.aspolygone, vous vous retrouverez avec un polygone. Son squelette gis.stackexchange.com/questions/177/… est ce dont vous avez besoin, je suppose. La mise en œuvre est un gros problème cependant
FelixIP
1
@Cyril, je peux revoir vos scripts ... La semaine prochaine. Publier quelque chose qui semble être une solution avec les fonctions PostGIS modernes sera une bonne première étape.
Peter Krauss

Réponses:

1

Je vais donc vous préparer un gâteau - plateau de fruits, en utilisant les outils PostGis, comme vous l'avez demandé, si j'ai bien compris la question, et comme je l'ai mentionné, la responsabilité du fonctionnement du four PostGIS est portée par son équipe créative.

Je vais demander à ne pas être offensé par quelqu'un dans mon style humoristique et à le comprendre comme un jeu!

Le fichier d'origine est constitué de fruits tranchés et de formes simples (ci-après appelés fruits), voir la figure 1 ci-dessous.

entrez la description de l'image ici

Voici ma recette, et je serai aidé en cela par de chers programmeurs, dont vous apprendrez plus tard. Commençons, et pour cela nous allons créer une pâte dans laquelle seront déposés nos fruits, pour laquelle exécuter le script:

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

Voir le résultat dans la figure 2 ci-dessous

entrez la description de l'image ici

Maintenant, s'il y a peu de fruits, comme dans mon image, créez la bordure du tampon externe sur le fruit, ou s'il y a beaucoup de fruits, créez la bordure du tampon négatif, pour lequel exécutez le script:

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;

Et découpez les lignes tampons autour de chaque fruit

UPDATE poly_buff_dump SET geom=ST_RemovePoint(geom, ST_NPoints(geom)-1) WHERE ST_IsClosed(geom)=true; Voir le résultat dans la figure 3 ci-dessous

entrez la description de l'image ici

(En fait, je pensais qu'en conséquence j'obtiendrais des lignes brisées (comme dans un cercle), mais si les chiffres sont difficiles, parfois des ruptures sont obtenues, incorrectes, par exemple, un côté du rectangle est tombé, etc. )

Ensuite, vous devez diviser les lignes obtenues de manière pratique pour vous en segments égaux et en extraire des points

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

Résultat, voir figure 4 ci-dessous

entrez la description de l'image ici

Maintenant, lancez l'outil Voronoi, à cet endroit, j'ai utilisé l'outil suggéré par le lien MickyT: /gis//a/172246/120129 , à la suite de quoi vous aurez créé des tables avec le nom "voronoi "Pour le fait que" mon premier assistant "est distinct du chef merci du chef! :-).

La deuxième façon de cette étape consiste à exécuter la fonction ST_VoronoiPolygons.

Résultat, voir figure 5 ci-dessous

entrez la description de l'image ici

Maintenant, coupez les parties supplémentaires en exécutant le script:

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); Résultat, voir figure 6 ci-dessous.

entrez la description de l'image ici

Exécutez maintenant le script afin d'aligner le type de géodonnées dans LineString:

create table poly_voronoi_dump as SELECT (ST_Dump(geom)).geom as geom FROM poly_voronoi_cut; Et maintenant, je vais demander à "mon second compagnon" de prendre mes fonctions et de mélanger le gâteau wel (Jeff - /gis//a/785/120129 ), en le nivelant en une seule couche, et pour cela , merci à moi pour ça!

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 ) ); Il est maintenant temps pour moi de me mettre au travail, pour lequel je lance le script:

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; et un autre script:

create table poly_voronoi_union_area as SELECT ST_Union(ST_ConvexHull(ST_BuildArea(geom))) as geom FROM poly_voronoi_union GROUP BY id; voir figure 7 ci-dessous

entrez la description de l'image ici

Comme vous pouvez le voir sur l'image, nos coupes ont de petites couches, qui peuvent être supprimées, en option en utilisant ST_SnapToGrid (ou d'une autre manière):

Et enfin, nous allons couper nos fruits au four de notre tarte, je me suis même un peu fatigué debout devant le four, :-)

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); Résultat voir figure 8 entrez la description de l'image ici

Tout de ce jour, maintenant tout le monde apprendra à faire de délicieuses tartes - plateau de fruits. Servez-vous de tous et choisissez les morceaux que vous aimez, pour tous.

(Dommage que je ne puisse vraiment pas nourrir tout le monde, pas avec des gâteaux électroniques, mais avec de vrais gâteaux, peut-être que la faim finirait sur Terre ...)

Edit: La cerise sur le gâteau pourrait ressembler à ceci :-):

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;

ou

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;

Avec vous était bon et juste Mr.Baker, merci à tous et bonne chance,: -) ...

Solutions originales.

Ce script est appelé: ST_VoronoiDiagramsFromPolygons.

Cyril Mikhalchenko
la source
1
Salut, bonnes illustrations, et semble de bon résultat (!). Suggestion pour une brève discussion, voir la solution @geogeek, les étapes de QGis semblent ici les principales étapes de PostGIS ... Pourquoi e besoin de ST_Bufferet ST_ConvexHull? Il existe un algorithme alternatif?
Peter Krauss
1) Voir, ST_Buffer et sur les polygones sont créés afin de réduire les lignes de séparation entre les figures d'origine lors de l'application de la fonction Voronoi, par conséquent, plus la taille de tampon que vous pouvez spécifier est grande, plus les lignes de séparation seront construites en douceur comme une fonction Voronoi ... 2) ST_ConvexHull de la multitude de figures sur chaque polygone, le polygone dont nous avons besoin ... 3) Aujourd'hui, c'est ma vision de résoudre votre question, je ne sais pas ce qui va nous arriver à tous et nos décisions à l'avenir ...
Cyril Mikhalchenko
Une autre valeur importante des lignes tampons est qu'elles nous aideront à sélectionner des fragments à partir du résultat de la fonction des Voronoi pour créer des polygones combinés pour chaque forme ...
Cyril Mikhalchenko
Soit dit en passant, je salue l'amélioration du code et de l'approche, afin qu'ils n'aggravent pas le résultat ...
Cyril Mikhalchenko
1
Salut Cyril, je suis d'accord que ST_Buffer est une bonne option pour normaliser les courbes de niveau, parfait (!). À propos ST_ConvexHull, n'est qu'une curiosité, quel genre de résultats nous pouvons obtenir après la figure 6, poly_voronoi_unionsans ST_ConvexHull.
Peter Krauss
8

Postgis n'a pas de fonction dédiée pour voronoi, mais Qgis contient une fonction vornoi qui pourrait créer des polygones voronoi à partir de points, donc en utilisant qgis j'ai suivi les étapes suivantes pour obtenir ces résultats:

-faire des points à partir de polygones en utilisant des extract nodesfonctions.

-faire des polygones vornoi en utilisant les fonctions voroi dans Qgis.

-Faire une jointure spatiale dans Qgis.

-dissoudre les résultats.

entrez la description de l'image ici

geogeek
la source
1
Belle solution (!), Et merci à l'illustration. Pouvez-vous l'améliorer? Voir le rectangle de gauche ci-dessous, il y avait 4 points à Voronoi, et le centre du rectangle n'a pas de représentation, déformant sa région (les pertes se font vers le triangle) ... Peut-être améliorer est-il possible de faire un échantillonnage régulier de chaque polygone ... et peut-être aussi quelques points intérieurs.
Peter Krauss
J'utilise l'outil de densification dans ArcGIS. Cela améliore considérablement les polygones de proximité. +1
FelixIP
3

OK - J'y ai réfléchi un peu et j'ai trouvé que c'était comme quelque chose que j'ai regardé récemment.

Prenez vos polys de départ:

entrez la description de l'image ici

Générez un nouvel attribut avec un nombre (100 dans mon cas) Utilisez l'outil Vector-> Outils de recherche -> Points aléatoires à l'intérieur des polygones cela générera (100) points à l'intérieur de chaque polygone: entrez la description de l'image ici

Ensuite, Vector-> Outils de géométrie -> Voronoi pour générer des polys basés sur cette couche de points.

entrez la description de l'image ici

Vous pouvez maintenant utiliser l'outil Vector -> Spatial Query: Sélectionnez les points qui appartiennent à un polygone (ou à l'un des polygones) Utilisez l'outil de requête spatiale pour générer une sélection de vos polygones voronoi qui s'appliquent à ce polygone. Ajoutez un attribut au polygone voroni qui correspond au polygone d'intérêt. (Je viens d'utiliser 1,2,3,4)

Vous pouvez maintenant Vector-> Outils de géotraitement-> dissoudre en fonction de votre nouvel attribut.

entrez la description de l'image ici

AA
la source
Merci @AAmes (!), Les illustrations sont bonnes, et la méthode est une bonne alternative ... Mais la question concerne "un algorithme SQL (ou un spécifique pour PostGIS)" et maintenant, la prime sur l' utilisation de la fonction ST_VoronoiPolygons () , qui peut-être résoudre tous les problèmes en un seul clic ;-)
Peter Krauss
@AAmes Une recherche rapide révèle que cette méthode peut également être utilisée dans PostGIS. Comment créer des points aléatoires dans un polygone dans Postgis explique la création de points à partir de polygones et à partir de là, cela devrait être assez simple.
Phil G
Ma prime était pour vous, comme incitation (bienvenue ici!), Mais CETTE RÉPONSE EST GENRE pour la question et les exigences de prime.
Peter Krauss
Merci Peter, j'ai vu vos notes mais malheureusement je n'ai pas eu l'occasion de revenir et de les aborder. Je n'ai pas encore d'expérience dans PostGIS et cela m'aurait pris plus de temps que je n'en disposais pour donner une bonne réponse. J'espère que notre exploration de cet espace sera utile aux gens à l'avenir, peut-être que si je reçois une fissure chez PostGIS bientôt, je reviendrai et j'essayerai de nouveau pour l'entraînement!
AA
2

Les points aléatoires sont une bonne idée pour générer un polygone voronoi à partir de polygones, cela fonctionne plutôt bien, mais c'est assez mauvais pour les polygones proches les uns des autres: entrez la description de l'image ici entrez la description de l'image ici

ST_ApproximateMedialAxis est une autre bonne alternative si vous utilisez PostGIS: Calcul des diagrammes de Voronoi pour les polygones

Leo
la source