Construcción de un polígono en una zona accesible

Question

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

Tal vez alguien me puede ayudar a reducir el tiempo de cálculo necesario para construir los polígonos que visualizar las alcanzable áreas.

Pero espera... lo primero es lo primero!
Aquí es una visualización de los bordes que yo son el resultado del cálculo de mi isócrono: Estos bordes son almacenados en una tabla de base de datos PostGIS y son simples linestrings.

Lo que quiero mostrar al usuario se parece a esto: Nota desconectado áreas en el sur y muy al este de la imagen. Estos deben ser elaborados como áreas separadas (por lo que no permitió la fusión de 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

Yo ya hice algunos experimentos y también he leído un montón de documentación, pero no puedo encontrar una mejor solución.
En mi opinión, el gran problema es el uso de ST_Union (como se indica en la documentación de esta función puede ser lento). La cosa muy interesante es que la sustitución con ST_Collect parece lenta la ST_Buffer cálculo para que todos la siguiente consulta incluso más tiempo, aunque no rellenar las zonas entre los bordes (solo crea un buffer 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 del tiempo). Mi primera conclusión de este pequeño punto de referencia es que ST_Buffer se presenta inesperadamente lento cuando se trata de MultiLineStrings (incluso más lento que cuando la creación de buffers para cada línea y la fusión de los buffers - que en mis ojos es sólo extraño)

También probé el uso de alfa-formas (mediante la aplicación de pgRouting), pero ya que no hay valor de alfa para establecer (y de hecho no me gustaría que ahora realmente a qué valor se establece un valor) acabo de llegar de un gran polígono (por eso me gustaría perder las regiones en el sur y en el este como en regiones separadas que no es lo que quiero).
También ST_Polygonize (que fue la primera cosa que vino a mi mente) no produjo resultados útiles, pero tal vez me he perdido algo aquí...

Hay una mejor manera de crear el área que se muestra en PostGIS? Tal vez también por el uso de código java (stc) o del lado del cliente javascript de código (jsts)? De hecho, yo podría vivir con perder detalle mientras las áreas que se muestran en el resultado permanecer separados y el cálculo gets (mucho) más rápido...

Saludos,
Niko

Answer 1

Dejando de lado la GeoJSON la serialización, la siguiente toma alrededor de 6.3 segundos en mi laptop:

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

Mirando los datos en OpenJUMP, me di cuenta un poco de detalle en los segmentos de calle, con relación al nivel deseado de detalle en la salida. Parece que incluso en el de la mosca de la simplificación 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

el que trae las cosas a 2.3 segundos. Pensé que tal vez podría hacerlo mejor mediante el almacenamiento de la generalización de la geometría en una columna separada, en lugar de calcular sobre la marcha, pero que en realidad proporciona ningún beneficio adicional.

Según cuenta cuánto código que está dispuesto a escribir, usted ciertamente puede hacer mejor en Java, si no otra cosa, porque usted puede tomar ventaja de varios núcleos. (Para lo que vale, la STC realiza la operación anterior en 2.8 segundos). Un método podría ser extender CascadedPolygonUnion para realizar algunas de las operaciones de unión suceden en paralelo. (actualización - aquí es un ParallelCascadedPolygonUnion)

Me di cuenta de que en la muestra de los datos que los bordes se almacenan con referencias a su inicio y final de los nodos, es decir, tiene un pre-construido gráfico. Sospecho que puede generar estos polígonos mucho más rápidamente si usted trabaja en el gráfico, en lugar de los genéricos de la geometría de las operaciones. Por ejemplo, creo que se podría así que algo como esto:

1. identificar los componentes conectados de la gráfica
2. para cada componente, encontrar el nodo con el mínimo de la coordenada X (garantizado para estar en el exterior del componente)
3. paseo de los bordes de la pieza, siempre girando a la izquierda (o derecha) cuando sea posible. Esto le dará el anillo exterior de cada componente.
4. polygonize el anillo exterior y el tampón de forma adecuada.