Construyendo un polígono sobre un área accesible

10

Actualmente estoy trabajando en el campo de las isócronas y los algoritmos subyacentes. Lo que ahora causa problemas no es el cálculo de la isócrona en sí, sino la visualización de los resultados.
El resultado de mi algoritmo isócrono son puntos y aristas. De hecho, tengo una solución que funciona, pero para 3873 bordes y para 1529 nodos las cosas parecen tomar para siempre (alrededor de 2.0 segundos en mi computadora portátil Lenovo T440s que contiene una CPU Core i7 2015 y un SSD bastante rápido). En lugar de segundos quiero algo más como msec :-).

Tal vez alguien pueda ayudarme a reducir el tiempo de cálculo necesario para construir los polígonos que visualizan las áreas accesibles.

Pero espera ... lo primero es lo primero!
Aquí hay una visualización de los bordes que son el resultado del cálculo de mi isócrona: Resultado de cálculo de isócrona (esqueleto existente de cadenas lineales) estos bordes se almacenan en una tabla de base de datos PostGIS y son cadenas de líneas simples.

Lo que quiero mostrar al usuario se ve así: ingrese la descripción de la imagen aquí Tenga en cuenta las áreas desconectadas en el extremo sur y este de la imagen. Deben dibujarse como áreas separadas (por lo que no se permite la fusión aquí :-))

Actualmente estoy usando esta consulta:

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_MakePolygon(ST_ExteriorRing(ST_GeometryN(segments, generate_series(1, ST_NumGeometries(segments))))) AS polygons FROM (
        SELECT ST_Union(ST_Buffer("GEOMETRY", 20, 'quad_segs=2')) AS segments FROM my_edges AS a
    ) AS b
) AS c

Ya experimenté un poco y también leí mucha documentación, pero no puedo encontrar una solución mejor.
En mi opinión, el gran problema es el uso de ST_Union (como se indica en los documentos, esta función puede ser lenta). Lo muy interesante es que reemplazarlo con ST_Collect parece ralentizar el cálculo de ST_Buffer, de modo que la consulta siguiente lleva más tiempo, aunque no llena las áreas entre los bordes (solo crea un búfer alrededor de las líneas ):

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_Buffer(ST_Collect(ST_LineMerge("GEOMETRY")), 20, 'quad_segs=2') AS polygons FROM my_edges AS a
) AS b

Esto toma alrededor de 3.8 segundos en mi sistema (casi el doble de tiempo). Mi primera conclusión de este pequeño punto de referencia es que ST_Buffer se vuelve inesperadamente lento cuando se trata de MultiLineStrings (incluso más lento que cuando se crean buffers para cada línea y se fusionan los buffers, lo que a mis ojos es simplemente extraño)

También intenté usar formas alfabéticas (usando la implementación de pgRouting), pero dado que no hay un valor alfa para establecer (y de hecho, no realmente ahora a qué valor establecer dicho valor) solo obtengo un gran polígono ( entonces perdería las regiones en el sur y el este como regiones separadas, que no es lo que quiero).
Además, ST_Polygonize (que fue lo primero que se me ocurrió) no produjo ningún resultado utilizable, pero tal vez me perdí algo aquí ...

¿Hay una mejor manera de crear el área que se muestra en PostGIS? ¿Quizás también usando código java (jts) o código javascript del lado del cliente (jsts)? De hecho, podría vivir perdiendo algunos detalles siempre que las áreas que se muestran en mi resultado permanezcan separadas y el cálculo sea (mucho) más rápido.

Nikolaus Krismer
fuente
¿No puede simplemente usar ST_Exteriorring (ST_Dump (ST_Union (ST_Buffer (geom, ....))). Geom ya que todo lo almacenado será un polígono de todos modos, y ST_Union conectará todas las geometrías de intersección, por lo que no hay necesidad de MakePolygon o GeometryN. Es posible que deba probar las cadenas de líneas que a veces resultan de ST_Union después de un búfer, pero eso es fácil con ST_GeometryType (geom). En lo que respecta al uso de Java o jsts, puede hacerlo, pero es poco probable que sea más rápido, dado que Gran parte de las funciones de Postgis (GEOS) son puertos C / C ++ de JTS en primer lugar
John Powell
Tiene razón, esto funciona, pero de hecho no es más rápido (toma ~ 3.1 segundos, mientras que el uso de GeometryN toma 2 segundos). Esto es lo que usé: SELECT ST_AsGeoJson (ST_Transform (ST_Exteriorring ((ST_Dump (ST_Union (ST_Buffer ("GEOMETRY", 20))). Geom), 4326)) FROM my_edges;
Nikolaus Krismer
@ john-barça: ¡Oh! Niego la parte quad_segs = 2 en el ST_Buffer cuando intento su enfoque ... con ese cambio, las consultas son pares (ambas alrededor de 2 segundos). Sin embargo, esto todavía es muy lento (a mis ojos), ¿hay otra forma de probarlo?
Nikolaus Krismer
Problema interesante ... ¿quieres compartir algunos datos de prueba?
dbaston
Si ayuda, estoy feliz de compartir algunos datos. Todas las cosas que hago aquí son de código abierto, por lo que esto no debería ser un gran problema. Lo primero que debe notar: una aplicación web para pruebas se encuentra en dbis-isochrone.uibk.ac.at:8080/testing . Puede encontrar más información sobre las cosas en las que trabajo en dbis-isochrone.uibk.ac.at . En la sección de "enlaces" del sitio web hay algunas referencias adicionales (incluidos algunos datos de prueba)
Nikolaus Krismer

Respuestas:

5

Dejando a un lado la serialización GeoJSON, lo siguiente toma alrededor de 6.3 segundos en mi computadora portátil:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(geom, 20, 2)))).geom))
FROM bz_edges

Al observar los datos en OpenJUMP, noté un poco de detalle en los segmentos de la calle, en relación con el nivel de detalle deseado en la salida. Parece que incluso una simplificación sobre la marcha de estas líneas puede producir una gran aceleración en PostGIS:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(ST_Simplify(geom, 10), 20, 2)))).geom))
FROM bz_edges

lo que reduce las cosas a 2.3 segundos. Pensé que tal vez podría hacerlo mejor almacenando la geometría generalizada en una columna separada, en lugar de calcularla sobre la marcha, pero eso en realidad no proporcionó ningún beneficio adicional.

Dependiendo de la cantidad de código que esté dispuesto a escribir, es casi seguro que pueda hacerlo mejor en Java, por lo menos porque puede aprovechar múltiples núcleos. (Para lo que vale, JTS realiza la operación anterior en 2.8 segundos). Un enfoque podría ser extender CascadedPolygonUnionpara hacer que algunas de las operaciones sindicales sucedan en paralelo. (actualización: aquí hay una ParallelCascadedPolygonUnion )

Noté en los datos de muestra que los bordes se almacenan con referencias a sus nodos de inicio y final, es decir, tiene un gráfico preconstruido. Sospecho que puede generar estos polígonos mucho más rápidamente si trabaja desde el gráfico en lugar de utilizar operaciones de geometría genéricas. Por ejemplo, creo que podrías hacer algo como esto:

  1. Identificar los componentes conectados del gráfico
  2. para cada componente conectado, busque el nodo con la coordenada X mínima (garantizado para estar en el exterior del componente)
  3. camine los bordes del componente, siempre girando a la izquierda (o derecha) cuando sea posible. Esto le dará el anillo exterior de cada componente.
  4. poligonalice el anillo exterior y el tampón adecuadamente.
dbaston
fuente
Gracias ... la simplificación es una gran mejora e incluso "simple". Tomó el tiempo necesario en mi computadora portátil hasta 1,5 segundos. No es donde quiero estar, pero un poco mejor.
Nikolaus Krismer
Con respecto a su solución sugerida (puntos 1-4). Suena también muy simple y vale la pena intentarlo. Pensé en algo similar, pero estoy atrapado en el punto 1 (muy temprano :-)). ¿Cómo se identificarían los componentes conectados? (Lo único que se me ocurre es una consulta recursiva que también puede ser muy lenta).
Nikolaus Krismer
@NikolausKrismer Utilizo JGraphT y telar para tareas como esta. Si escribe sus propios métodos gráficos (no es una mala idea para obtener el mejor rendimiento), una búsqueda profunda le encontrará los componentes. (Puede encontrarlos en el próximo PostGIS 2.2 con, ST_ClusterIntersectingpero creo que querrá que se realice cualquier tipo de procesamiento gráfico fuera de la base de datos de todos modos, por lo que esto probablemente no sea útil).
dbaston
Estos son algunos buenos consejos. Miré a JGraphT y esto ciertamente podría ayudar a resolver mi problema. Sin embargo, también miré Postgis 2.2 y la función ST_ClusterIntersecting -> se necesitan entre 200 y 250 ms para identificar los diferentes grupos en el caso anterior. Eso está bien para mí (JGraphT ciertamente podría hacerlo mejor). Ahora tengo que lidiar con la creación del exteriorRing (ST_ExteriorRing falla, ya que ST_MakePolygon dice que mis enlaces no son shell)
Nikolaus Krismer
Veo dos complicaciones: (a) necesita no solo el anillo exterior, sino también cualquier segmento que se extienda hacia afuera desde ese anillo, y (b) parece que sus líneas no se cruzan en algunas intersecciones. Tendrá que corregir (b) si va a intentar construir una geometría a partir de los resultados de una caminata gráfica.
dbaston