Algoritmo de acumulación de distancia

Disponible con Image Server

Las herramientas Acumulación de distancia y Asignación de distancia sustituyen a las herramientas de coste-distancia heredadas. Estas nuevas herramientas miden el coste-distancia en todas las direcciones al reconstruir una superficie acumulativa continua en lugar de buscar rutas a través de una red de centros de celdas. Puede crear superficies de coste acumulativo de salida a partir de superficie de fricción de coste de entrada y otros parámetros. Al igual que con otras superficies, puede obtener una comprensión más precisa de los resultados agregando líneas de curvas de nivel (líneas de igual coste acumulativo), visualizarlas en 3D y visualizarlas en combinación con las cuencas hidrográficas de asignación. Normalmente, el objetivo de construir esta superficie es trazar las rutas de menor coste, que son rutas de descenso más empinado.

Superficie de coste acumulativo

El algoritmo utilizado por estas herramientas reconstruye una superficie a partir de su pendiente.

Planteamiento de reconstrucción de superficie

Con las herramientas Acumulación de distancia y Asignación de distancia, buscar el menor coste acumulativo ya no es un problema de red. El ráster de costes acumulativo de salida es una superficie con una forma desconocida. Desea descubrir la forma solo con su pendiente en cada celda del área de estudio. Este enfoque utiliza conceptos de geometría diferencial para calcular la distancia y los costes reales en todas las direcciones.

La superficie de coste acumulativo responde a tres preguntas importantes:

  • ¿En qué lugar el coste aumenta rápidamente como función de la distancia?
  • ¿Qué celdas de origen están más cerca de una celda determinada que no pertenece al origen?
  • ¿Qué ruta debería seguirse desde una celda que no pertenece al origen hasta la celda de origen más cercana?

Puede utilizar las vistas 3D y líneas de curvas de nivel con la superficie de salida para encontrar las respuestas a estas preguntas. Puede utilizar las herramientas Asignación de distancia y Ruta óptima como línea para obtener respuestas más precisas.

Las siguientes subsecciones describen la relación entre una superficie de fricción de coste de entrada simple y la superficie de coste acumulativo de salida.

Superficie de fricción de coste de entrada simple

Considere un ráster de fricción de coste simple que tenga una sección central con coste = 3, una sección central con coste = 2 y una sección externa con coste = 1.

Ráster de fricción de coste como anillos concéntricos
Se muestra una entrada de ráster de fricción de coste como anillos concéntricos con un punto que indica el centro.

La interpretación 3D se puede usar para comprender la relación entre el ráster de fricción de coste y la superficie de coste acumulativo de salida. La altura h de la superficie en la celda c es la suma de las pendientes del ráster de costes de entrada multiplicada por las distancias sobre las cuales están activas esas pendientes (h = 3 * d1 + 2 * d2 + 1 * d3).

Representación 3D del ráster de fricción de coste y la relación de superficie de coste acumulativo de salida
La relación entre la entrada de fricción de coste y la superficie de coste acumulativo de salida se muestra en una representación 3D.

Una vista de planta de la misma superficie de salida muestra cómo las líneas de curvas de nivel representan el cambio de coste acumulativo. También se muestran los valores de pendiente y orientación en la ubicación de celda c. La orientación (la dirección del descenso más empinado) siempre se encuentra en ángulos rectos con respecto a la línea de curvas de nivel.

Las líneas de curvas de nivel representan cómo cambia el coste acumulativo
Las líneas de curvas de nivel muestran cómo cambia el coste acumulativo en una vista de planta de la superficie ráster.

Incorporar el menor coste acumulativo

A continuación, se muestra un caso algo más complicado. El coste acumulativo (elevación) en una celda que no pertenece al origen provendrá del origen que llega a esa celda con el menor coste.

El ráster de costes tiene dos valores: 1 como gris claro y 3 como gris oscuro. Los puntos de origen son S1 y S2. La celda D no perteneciente al origen está más cerca de S1 en términos de coste acumulativo.

Ráster de costes con puntos de origen S1 y S2 y celda de origen D
Un ráster de costes de entrada se superpone con los puntos de origen de entrada y una celda de origen.

Agregar líneas de curvas de nivel a la superficie de coste acumulativo puede ayudarle a visualizar lo rápido que cambia el coste a medida que se aleja de los orígenes. Desde la ubicación que no es de origen y moviéndose en ángulos rectos a las líneas de curvas de nivel, se desplaza de vuelta a la celda de origen más cercana. La ruta no va al origen más cercano geométricamente debido al coste alto alrededor de ese origen.

Vista de planta de una superficie de coste acumulativo para dos orígenes
Se muestra una vista de planta de la superficie de menor coste acumulativo para dos orígenes (S1 y S2) desde una ubicación que no es de origen.

A continuación, se encuentra una vista 3D que muestra la misma superficie de menor coste acumulativo. La superficie es mucho más empinada alrededor del origen costoso (los costes se acumulan más rápidamente). Ese origen posee la mínima superficie de coste solo muy cercana a ella. En el resto de celdas del área de estudio, la superficie pertenece al origen de la izquierda.

Representación 3D de una superficie de menor coste acumulativo
Se muestra una vista en perspectiva 3D de una superficie de menor coste acumulativo para dos orígenes.

Asignar regiones como cuencas hidrográficas

A medida que la superficie de fricción de coste de entrada y la superficie de coste acumulativo de salida se vuelven más complicadas, aún puede utilizar líneas de curvas de nivel, pendiente y orientación para comprender el comportamiento de las superficies de coste acumulativo. Además, las regiones de asignación alrededor de los orígenes funcionan como cuencas hidrográficas en la superficie de salida de coste acumulativo. Todas las rutas de menor coste de una región de asignación fluyen hacia el mismo origen. Las cuencas hidrográficas de asignación se combinan con líneas de curvas de nivel y una vista 3D en los ejemplos siguientes.

Las superficies de coste acumulativo más complicadas, como esta superficie de tiempo de viaje, se pueden visualizar con precisión en 2D y 3D mediante líneas de curvas de nivel (isócronas en este caso).

Superficie de coste acumulativo con líneas de curvas de nivel en 2D
Se muestra una superficie de coste acumulativo con líneas de curvas de nivel en una vista de planta 2D.

En la siguiente imagen se muestra una vista 3D de la misma superficie. Los acantilados en segundo plano son barreras causadas por la presencia de un río.

Superficie de coste acumulativo en vista en perspectiva 3D
Se muestra una vista en perspectiva 3D de una superficie de coste acumulativo.

Las rutas de menor coste fluyen por la superficie de coste acumulativo hacia el origen que define la zona de asignación (cuenca hidrográfica), como se muestra en la siguiente imagen:

Perspectiva 3D del flujo de las rutas de menor coste
Se muestra una vista en perspectiva 3D del flujo de las rutas de menor coste hacia la superficie de coste acumulativo.

El algoritmo de reconstrucción de superficie es una extensión del algoritmo de red

Para buscar una superficie de coste acumulativo únicamente sabiendo el valor de la pendiente más empinada en cada celda, también puede utilizar el algoritmo de reconstrucción de superficie. Este algoritmo es similar al algoritmo de ruta más corta utilizado por las herramientas de coste-distancia heredadas, pero con un paso adicional para proporcionar una aproximación de coste acumulativo que no sigue una de las ocho direcciones de red. Se denomina paso eikonal. Dispone a continuación de una breve descripción y encontrará más información en Sethian, 1999.

Para entender este paso en contexto, encontrará el coste acumulativo z5 para la celda central de a continuación. Suponga que conoce todos los costes acumulativos vecinos zi. Además, desde el ráster de costes de entrada, conoce el valor de pendiente S en la celda central.

Cuadrícula 3 por 3 con altura de celda central
Figura 4. El algoritmo de reconstrucción de superficie calcula una altura z5 para la celda central al realizar varias aproximaciones para esa altura con la pendiente del ráster de fricción de coste de entrada en la celda central, junto con alturas conocidas zi asumidas para las celdas vecinas.

Por ejemplo, una aproximación para z5 puede ser a lo largo de la diagonal entre z3 y z5, donde z5 = z3 + 1,4 * tamaño de celda * S, como se muestra en la siguiente figura. En este caso, S (el valor del ráster de costes de entrada) se interpreta como la pendiente del triángulo abc. Para toda la aproximación del estilo de red, solo se utiliza la pendiente en z5 para aproximar el coste acumulativo en z5. Es diferente al algoritmo de red heredado, que utiliza un promedio de costes de pares de celdas.

Cálculo de pendiente diagonal para una celda
Figura 5. Se muestra un cálculo de paso diagonal. La pendiente s de la superficie de fricción de coste de entrada se interpreta como la pendiente de la hipotenusa del triángulo abc.

Se pueden realizar ocho aproximaciones de red, incluidas cuatro que utilicen pares de alturas existentes, como se muestra en la secuencia de las tres figuras siguientes. En este caso, el valor del ráster de costes de entrada en la ubicación de la celda z5 se interpreta como la magnitud S del gradiente del plano que pasa por los dos puntos conocidos y la elevación desconocida z5. Desde esta relación, puede resolver z5. Este es el paso eikonal.

Entradas del paso eikonal
Figura 6. Se muestran las entradas del paso eikonal: se conocen dos alturas, z6 y z8.

Se calcula la magnitud del gradiente del plano.

La medida S es la magnitud del gradiente del plano
Figura 7. La medida S desde el ráster de costes es la magnitud del gradiente del plano que atraviesa las dos elevaciones conocidas z8 y z6 y la elevación desconocida z5

Se calcula la dirección del gradiente.

La dirección del gradiente es el valor de orientación (dirección hacia atrás)
Figura 8. La dirección del gradiente es el valor de orientación (dirección hacia atrás) de la celda z5.

El paso eikonal también recupera la información de orientación en z5, que se denomina dirección hacia atrás.

Ahora hay doce aproximaciones para la elevación en la celda central. El mínimo de ellos se selecciona y se registra como el valor de coste acumulativo z5 para la celda central. Si solicitó un ráster de dirección hacia atrás, la orientación del gradiente (como se describe en el párrafo anterior) se registra en la ubicación correspondiente en el ráster de dirección hacia atrás de salida.

Este proceso se repite para una celda cada vez que se obtiene un nuevo valor de elevación para uno de sus vecinos. Finalmente, los valores de elevación dejan de cambiar y el algoritmo termina. Las elevaciones iniciales las proporcionan los orígenes: son cero o el valor de acumulación inicial por origen. El resto de valores de elevación iniciales se establecen en infinito. Los detalles se describen en Sethian (1999). La implementación de Esri de esto es una combinación de técnicas que se describen en Sethian (1999) y Zhao (2004).

En resumen, empezando desde la pendiente de cada celda, estos pasos reconstruyen tanto la elevación de la superficie de coste acumulativo como la dirección del descenso más empinado.

Rutas de menor coste

Las rutas de menor coste siguen la dirección cuesta abajo más empinada por la superficie de coste acumulativo. Esa dirección, para una celda, se muestra anteriormente en la figura 8. El ráster de dirección hacia atrás de salida almacena esa dirección para cada celda. Puede utilizar la herramienta Ruta óptima como línea con el ráster de dirección hacia atrás como entrada, a fin de trazar esas rutas desde cualquier celda no perteneciente al origen.

En las siguientes figuras, se muestra una ruta de menor coste curvada que comienza desde la celda d azul no perteneciente al origen en la parte superior derecha y se desplaza hacia la celda de origen inferior s. Mientras que d está geométricamente más cerca del origen superior, debido al coste elevado alrededor de ese origen, es más barato viajar a s siguiendo la ruta curvada.

El destino d es el cuadrado azul. Viaja a través de un área de menor coste hasta el origen que puede alcanzar de manera más barata, curvándose alrededor del origen de coste alto para hacerlo.

Los círculos muestran la construcción de la ruta de menor coste
Figura 9. Se muestra la construcción de las rutas de menor coste con una superficie de coste acumulativo construida a partir de la superficie de fricción de coste de entrada de la Figura 3.

Aunque puede parecer que el nombre es poco intuitivo, las ubicaciones de entrada para la construcción de la ruta de menor coste se denominan destinos. Los orígenes se utilizaron para construir la superficie y son las ubicaciones donde terminan las rutas de menor coste.

Las zonas de asignación alrededor de los orígenes explican aún más que la ruta de menor coste desde el destino viajará al origen inferior y no al origen superior. A continuación, se acercará al área seleccionada para mostrar cómo se interpretan los valores de celda en el ráster de dirección hacia atrás.

Ubicación del área de estudio resaltada por un cuadrado
La ubicación del área de estudio está marcada por el cuadro.

El lattice que conecta los centros de celda de dirección hacia atrás se muestra en gris oscuro. Los límites de la celda se muestran en gris claro y los valores de celda se muestran como flechas de acimut. Dado que la ruta de menor coste cruza las líneas de lattice, utiliza el acimut en la celda de dirección hacia atrás más cercana en la dirección de viaje para actualizar su dirección. En el vértice de ruta superior al lado de la celda a, el valor de dirección hacia atrás almacenado en a se utilizará para dirigir la línea dejando ese vértice. La siguiente línea de lattice que se va a cruzar es la más cercana a la celda b, de modo que el acimut se utilizará para salir del segundo vértice, y así sucesivamente.

Cuadrícula de lattice de valores de celda del ráster de dirección hacia atrás
Se muestra una vista de lattice de cómo se interpretan los valores de celda en el ráster de dirección hacia atrás.

En resumen, las rutas de menor coste comienzan y finalizan en los centros de las celdas. Otros vértices de ruta pueden estar en cualquier lugar del lattice de líneas horizontales y verticales que recorren los centros de las celdas.

Cálculo de pendiente eficaz

Los valores de pendiente descritos en la sección anterior no provienen estrictamente del ráster de fricción de coste de entrada. Existen otras entradas que, juntas, determinan la pendiente efectiva utilizada por el algoritmo de reconstrucción de superficie. En otros temas se presenta una descripción detallada de estas entradas, incluida la importancia de tener en cuenta la dirección del movimiento a través de una celda y la dirección de viaje desde un origen o hasta él. Aquí, el énfasis se centra en cómo se utilizan las entradas en el algoritmo de reconstrucción de superficie. Estas son las entradas:

  • La entrada de fricción de coste, C
  • La entrada de superficie, S
  • El multiplicador de coste de origen, M
  • La función de factor horizontal, HF
  • La función de factor vertical, VF

La pendiente efectiva utilizada por el algoritmo de reconstrucción tiene esta forma general:

Pendiente efectiva = C * S * M * HF * VF

A continuación, este valor se multiplica por el tamaño de celda o sqrt(2) * tamaño de celda y se suma a una altura existente para obtener una de las estimaciones de altura de dirección de red. Se utiliza una función más complicada de pendiente efectiva para obtener una estimación de altura para el paso eikonal.

La pendiente efectiva debe tener unidades de coste acumulativo divididos por la distancia lineal, una tasa. Por ejemplo, si la superficie de coste acumulativo es medir el tiempo de viaje en horas y el tamaño de celda del análisis está en metros, la pendiente efectiva debe tener unidades de horas/metro.

Dado que la pendiente efectiva es resultado de varios términos, debe asegurarse de que las unidades de los términos individuales se combinen para producir las unidades de pendiente efectivas correctas. Por ejemplo, si está utilizando solo un ráster de fricción de coste simple para describir el tiempo de viaje independientemente de la dirección, los valores de la celda ráster de fricción de coste deben tener unidades de horas/metro. Como alternativa, si también utiliza la función de senderismo de Tobler como función de factor vertical, esta función de senderismo tendrá unidades de horas/metro y la superficie de fricción de coste, si la hay, debe interpretarse como un peso sin unidades. A continuación, debe asegurarse de que los valores de la celda de fricción de coste se puedan interpretar de esa manera. En otras palabras, la función vertical y la fricción del coste no pueden ser tasas.

No controla directamente la entrada de superficie (S). Es un peso sin unidades que extiende el tamaño de celda para abarcar la distancia de superficie 3D real entre los centros de las celdas. En la Figura 2, el algoritmo de reconstrucción de superficie calcula una altura z5 para la celda central al realizar varias aproximaciones para esa altura con la pendiente del ráster de fricción de coste de entrada en la celda central, junto con alturas conocidas asumidas para las celdas vecinas.

Las barreras están conectadas a los ejes

Las barreras en las herramientas Acumulación de distancia y Asignación de distancia son celdas de entrada por las que no se puede pasar. Se representan como celdas NoData durante el cómputo. Se presentan de manera explícita como un parámetro de la herramienta o implícita como valores NoData en una de las otras entradas de ráster (como el ráster de fricción de coste). En el primer caso, se rasterizan y se convierten en NoData en el ráster de costes. Dado que el algoritmo de reconstrucción de superficie no puede reducir la estimación de altura de una celda de barrera, encontrará una forma de rodearla.

El algoritmo de reconstrucción de superficie utiliza los ocho vecinos de una celda para determinar su estimación de altura. Los vecinos de barrera conectados por esquinas no impedirán que se utilice un vecino diagonal para obtener una estimación de altura. En la siguiente imagen, se puede obtener una estimación de altura para z5 desde z3, incluso si las celdas z2 y z6 son barreras.

Cuadrícula con barreras conectadas por esquinas

Si se intentara que z2 y z6 formasen parte de una entidad de barrera lineal, como un canal o un río, este comportamiento podría impedir el intento de la barrera. Para evitarlo, el algoritmo de reconstrucción superficie facilita la conexión de celdas de barrera a través de la conexión de celdas que no sean de barrera. Significa que las celdas NoData adicionales se introducen en el ráster de costes para garantizar que todas las celdas de barreras existentes compartan un borde. En la imagen anterior, la celda z5 o la celda z3 también se convertirían en celdas de barrera.

Al utilizar barreras en el análisis, tenga en cuenta este comportamiento y ajuste el tamaño de celda del análisis en consecuencia para que se conserve la conectividad prevista alrededor de las barreras. Puede utilizar la herramienta Estadísticas focalizadas para ensanchar las versiones de ráster de las entidades lineales a fin de utilizarlas como barreras o como redes lineales, que no deberían ser interrumpidas por las celdas de barrera adyacentes.

Referencias

Douglas, D. "Least-cost Path in GIS Using an Accumulated Cost Surface and Slopelines", Cartographica: The International Journal for Geographic Information and Geovisualization, 1994, Vol. 31, N.º 3, DOI: 10.3138/D327-0323-2JUT-016M

Goodchild, M.F. "An evaluation of lattice solutions to the problem of corridor location", Environment and Planning A: Economy and Space, 1977, vol. 9, páginas 727-738

Sethian, J.A. Level Set Methods and Fast Marching Methods (Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science) 2nd Edition, Cambridge University Press, 2.ª edición (1 de junio de 1999)

Warntz, W. "Transportation, Social Physics, and the Law Of Refraction", The Professional Geographer, 1957, Vol. 9, N.º 4, páginas 2-7.

Zhao, H. "A fast sweeping method for Eikonal equations", Mathematics of Computation, 2004, Vol. 74, N.º 250, páginas 603-627