Crear un mosaico como el Diagrama de Voronoi a partir de polígonos disjuntos

Question

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 de 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 genera 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 el de Voronoi, que la delimitación del espacio (un marco cuadrado en (b) ) se ignora.

---

Este problema es similar al de este otro sobre líneas .

EDITAR (tras el comentario de @FelixIP)

Prefiero quedarme en vector universo, para no perder precisión (por ejemplo, utilizando ST_DelaunayTriángulos y sumando y restando interiores por los polígonos originales, adaptándolos a solución gráfica dual )... Algunos paquetes simples y automáticos como ppreparar (asistido como Herramientas topológicas de QGIS no son automáticas). Pero raster 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 pueda 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 Así que, tal vez haya un Solución similar a PostGIS empezando por el conjunto de polígonos (clasificar, rasterizar y hacer retroceder los polígonos).

Answer 1

Postgis no tiene una función dedicada a voronoi, pero Qgis contiene la función vornoi que podría hacer polígonos voronoi a partir de puntos, así que usando qgis he seguido los siguientes pasos para tener este resultado:

-hacer puntos a partir de polígonos utilizando extract nodes funciones.

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

-Hacer una unión espacial en Qgis.

-disolver los resultados.

Answer 2

OK - Pensé en esto un poco y encontré que era como algo que he estado mirando últimamente.

Toma tus polos iniciales:

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

Luego Vector-> Geometry tools -> Voronoi para generar polys basados en esa capa de puntos.

Ahora, puede utilizar la herramienta Vector -> Spatial Query: Seleccione los puntos que pertenecen a un polígono (o a uno de los polígonos) Utilice la herramienta de consulta espacial para generar una selección de sus polígonos de voronoi que se aplican a ese polígono. Añade un atributo al polígono de voronoi que corresponda al polígono de interés. (Yo sólo he utilizado 1,2,3,4)

Ahora puede Vector-> Herramientas de geoprocesamiento-> disolver en base a su nuevo atributo.

Answer 3

Por lo tanto, voy a preparar un pastel para usted - plato de frutas, utilizando las herramientas de PostGIS, como usted pidió, si he entendido correctamente la pregunta, y como he mencionado, la responsabilidad del funcionamiento del horno PostGIS es de su equipo creativo.

Pediré que nadie se ofenda con mi estilo humorístico y que lo entiendan como un juego.

El archivo original es una fruta cortada en rodajas y formas simples (en lo sucesivo, fruta), véase la figura 1.

Esta es mi receta, y para ello contaré con la ayuda de queridos programadores, a los que conoceréis más adelante. Vamos a empezar, y para ello vamos a crear una masa en la que se colocarán nuestras frutas, para lo cual ejecutar el script:

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

Véase el resultado en la figura 2

Ahora, si hay pocas frutas, como en mi foto, crea el borde del buffer externo sobre la fruta, o si hay muchas frutas, crea el borde del buffer negativo, para lo cual ejecuta 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 cortar 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; Véase el resultado en la figura 3

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

A continuación, hay que dividir las líneas obtenidas de forma conveniente para usted en segmentos iguales y extraer puntos de ellos

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

Resultado, véase la figura 4

Ahora ejecuta la herramienta Voronoi, en este lugar he utilizado la herramienta sugerida por el enlace MickyT : https://gis.stackexchange.com/a/172246/120129 como resultado 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, véase la figura 5

Ahora, corta las partes sobrantes 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, véase la figura 6 más abajo.

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 pediré a "mi segundo" que asuma mis funciones y mezcle el pastel wel (Jeff - https://gis.stackexchange.com/a/785/120129 ), nivelándolo en una sola capa, y por eso, ¡gracias a mí por ello!

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 ponerme a 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; véase la figura 7 a continuación

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

Y por último, recortaremos nuestra fruta horneada de nuestra tarta, incluso me cansé un poco de estar al lado del 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 a partir de este día, ahora todo el mundo aprenderá a hornear deliciosos pasteles - plato de frutas. Ayudarse a sí mismo Todo, y elegir las piezas que, comosuficiente para todos.

(Es una pena que realmente no pueda alimentar a toda la gente, no con pasteles electrónicos, sino con pasteles de verdad, quizás se acabaría el hambre en la Tierra...)

Editar: La guinda del pastel podría tener este aspecto :-) :

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;

Revisar guión 01.04.2020:

WITH tbla AS (
WITH atbl AS (SELECT id, (ST_ExteriorRing(((ST_Dump(geom)).geom))) geom FROM polygons),
intervals AS (SELECT generate_series (0, 501) as steps)
SELECT steps AS stp, ST_LineInterpolatePoint(geom, steps/(SELECT count(steps)::float-1 FROM intervals)) geom FROM atbl, intervals GROUP BY id, intervals.steps, geom),
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;

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

Soluciones originales.

Este script se llama: ST_VoronoiDiagramsFromPolygons.

Editar:

¡¡¡La función SQL puede tener este aspecto por ahora y sólo para una tabla y un pequeño conjunto de datos!!!

CREATE OR REPLACE FUNCTION ST_VoronoiDiagramsFromPolygons(
   geom GEOMETRY,
    n integer)
RETURNS TABLE (id bigint, geom GEOMETRY) AS  
$BODY$
WITH
tbla AS (SELECT row_number() over() AS id, ((ST_Dump(geom)).geom) geom FROM polygons),
tblb AS (WITH btbl AS (SELECT id, ST_ExteriorRing((ST_Dump(geom)).geom) geom FROM tbla GROUP BY id, geom),
    intervals AS (SELECT generate_series (0, n) as steps)
    SELECT steps AS stp, ST_LineInterpolatePoint(geom, steps/(SELECT count(steps)::float-1 FROM intervals)) geom FROM btbl, intervals GROUP BY id, stp, intervals.steps, geom),
tblc AS (SELECT (ST_Dump(ST_VoronoiPolygons(ST_Collect(geom)))).geom geom FROM tblb)
    SELECT b.id, ST_Union(a.geom) geom FROM tblc a JOIN tbla b ON ST_Intersects(a.geom, b.geom) GROUP BY id;
$BODY$
LANGUAGE SQL

RUN

SELECT DISTINCT (ST_VoronoiDiagramsFromPolygons(geom, 300)).* geom FROM polygons ORDER BY id;

Quizá algún día los desarrolladores de PostgreSQL y PostGIS actualicen su comportamiento

Answer 4

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

ST_ApproximateMedialAxis es otra buena alternativa si se utiliza PostGIS: Cálculo de diagramas de Voronoi para polígonos

Answer 5

He publicado un mini paquete de python para hacerlo - voronoi-diagram-for-polygons . Hay que señalar de antemano que este paquete depende de la versión v1.8.dev0 de elegante que aún está en desarrollo. En otras palabras, la dependencia de voronoi-diagram-for-polygons no puede ser instalado por pip automáticamente. Tiene que instalar la última Shapely en primer lugar por lo siguiente:

pip install git+https://github.com/Toblerity/Shapely .