Cree mosaicos como el diagrama de Voronoi a partir de polígonos disjuntos

La siguiente ilustración muestra el problema :

como en (a) tengo un conjunto de polígonos disjuntos, como geometrías en PostGIS. Necesito algo como (b) , el "mosaico" de este conjunto de polígonos, construyéndolo por un criterio de "región de influencia" ... Es como una construcción Voronoi (ilustrada por (c) ): de hecho, si los polígonos eran puntos, las regiones de influencia son Voronoi.

Resumiendo: Necesito un algoritmo SQL (o alguno específico para PostGIS) que genere el "mosaico" de un conjunto de polígonos disjuntos. (quizás un bucle de pequeñas operaciones ST_Buffer y ST_Difference)

PD: Necesito, como Voronoi, que la delimitación del espacio (un cuadro cuadrado en (b) ) se ignore.

Este problema es similar a este otro sobre líneas .

EDITAR (después del comentario de @FelixIP)

Prefiero permanecer en el universo vectorial , para no perder precisión (por ejemplo, usando ST_DelaunayTriangles y sumando y restando interiores por los polígonos originales, adaptando una solución de gráfico dual ) ... Algunos paquetes simples y automáticos como pprepair (asistido como herramientas topológicas QGIS) No son automáticos). Pero la trama es quizás más simple y consume menos CPU.

Esta ilustración del "proceso GRID" también es válida como solución, suponiendo que puede permitir la misma precisión y el "crecimiento de la región de influencia euclidiana".

En ARCGIS existe una herramienta de análisis espacial conocida como Asignación Euclidiana , por lo tanto, tal vez exista una solución similar a PostGIS , comenzando con el conjunto de polígonos (clasificación, rasterización y recuperación de los polígonos).

Por lo tanto, prepararé un pastel para usted: bandeja de frutas, utilizando las herramientas de PostGis, como solicitó, si entendí correctamente la pregunta, y como mencioné, la responsabilidad de la operación del horno PostGIS corre a cargo de su equipo creativo.

¡Pediré que nadie me ofenda con mi estilo humorístico y que lo entienda como un juego!

El archivo original es fruta en rodajas y formas simples (en adelante denominadas fruta), vea la Figura 1 a continuación.

Aquí está mi receta, y me ayudarán en esto los estimados programadores, de quienes aprenderán más adelante. Comencemos, y para esto crearemos una masa en la que se colocarán nuestros frutos, para lo cual ejecutaremos el script:

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

Vea el resultado en la Figura 2 a continuación

Ahora, si hay pocas frutas, como en mi imagen, cree el borde del búfer externo en la fruta, o si hay muchas frutas, cree el borde del búfer negativo, para lo cual ejecute el 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;

Y corta las líneas de amortiguación alrededor de cada fruta

UPDATE poly_buff_dump SET geom=ST_RemovePoint(geom, ST_NPoints(geom)-1) WHERE ST_IsClosed(geom)=true; Vea el resultado en la Figura 3 a continuación

(En realidad, pensé que como resultado obtendría líneas discontinuas (como en un círculo), pero si las figuras son difíciles, a veces se obtienen saltos, incorrectos, por ejemplo, un lado del rectángulo se cayó, etc. )

Luego debe dividir las líneas obtenidas de manera conveniente para usted en segmentos iguales y extraer puntos de ellas

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

Resultado, ver Figura 4 a continuación

Ahora ejecute la herramienta Voronoi, en este lugar utilicé la herramienta sugerida por el enlace MickyT: /gis//a/172246/120129 , como resultado de lo cual habrá creado tablas con el nombre "voronoi "Por el hecho de que" mi primer asistente "está separado del chef gracias al chef! :-).

La segunda forma en este paso es ejecutar la función ST_VoronoiPolygons.

Resultado, ver Figura 5 a continuación

Ahora, corte las partes adicionales ejecutando el 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); Resultado, ver Figura 6 a continuación.

Ahora ejecute el script para alinear el tipo de geodatos en LineString:

create table poly_voronoi_dump as SELECT (ST_Dump(geom)).geom as geom FROM poly_voronoi_cut; Y ahora le pediré a "mi segundo compañero" que asuma mis deberes y mezcle bien el pastel (Jeff - /gis//a/785/120129 ), nivelando en una sola capa, y para eso ¡Gracias a mí por eso!

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 ) ); Ahora es el momento de trabajar, para lo cual ejecuto el 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; y otro guión:

create table poly_voronoi_union_area as SELECT ST_Union(ST_ConvexHull(ST_BuildArea(geom))) as geom FROM poly_voronoi_union GROUP BY id; ver figura 7 a continuación

Como puede ver en la imagen, nuestros cortes tienen capas pequeñas, que se pueden eliminar, como una opción usando ST_SnapToGrid (o de otra manera):

Y finalmente, cortaremos nuestra fruta horneada de nuestro pastel, incluso me cansé un poco de pie junto al horno :-)

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); Resultado ver figura 8

Todo desde este día, ahora todos aprenderán a hornear deliciosos pasteles: bandeja de frutas. Ayúdate a ti mismo y elige las piezas que más te gusten para todos.

(Es una pena que realmente no pueda alimentar a todas las personas, no con pasteles electrónicos, sino con pasteles reales, tal vez el hambre terminaría en la Tierra ...)

Editar: La guinda del pastel podría verse así :-):

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;

o

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;

Contigo fue bueno y justo Mr.Baker, gracias a todos y buena suerte,: -) ...

Soluciones originales

Este script se llama: ST_VoronoiDiagramsFromPolygons.

Los postgis no tienen una función dedicada para voronoi, pero Qgis contiene la función vornoi que podría hacer polígonos de voronoi a partir de puntos, por lo que usando qgis he seguido los siguientes pasos para obtener estos resultados:

-Hacer puntos a partir de polígonos usando extract nodesfunciones.

-Hacer polígonos de vornoi usando las funciones de voroi en Qgis.

-hacer una unión espacial en Qgis.

-disolver resultados.

OK - Pensé un poco en esto y descubrí que era algo que he estado viendo últimamente.

Tome sus polys iniciales:

Generar un nuevo atributo con un número (100 en mi caso) Use la herramienta Vector-> Herramientas de investigación -> Puntos aleatorios dentro de polígonos, esto generará (100) puntos dentro de cada polígono:

Luego, Vector-> Herramientas de geometría -> Voronoi para generar polys basados ​​en esa capa de puntos.

Ahora, puede usar la herramienta Vector -> Consulta espacial: Seleccione los puntos que pertenecen a un polígono (o uno de los polígonos) Use la herramienta de consulta espacial para generar una selección de sus polígonos voronoi que se aplican a ese polígono. Agregue un atributo al polígono voroni que corresponda al polígono de interés. (Acabo de usar 1,2,3,4)

Ahora puede Vector-> Herramientas de geoprocesamiento-> disolver según su nuevo atributo.

Los puntos aleatorios son una buena idea para generar un polígono voronoi a partir de polígonos, funciona bastante bien, pero es bastante malo para polígonos cercanos entre sí:

ST_ApproximateMedialAxis es otra buena alternativa si se usa PostGIS: Calcular diagramas de Voronoi para polígonos