Cómo funcionan las herramientas de coste de distancia

Todas las herramientas de coste de distancia utilizan esencialmente el mismo algoritmo para calcular la salida. La diferencia esencial esta determinada por la salida primaria de cada herramienta.

Cálculo de la distancia de coste

La herramienta Coste de distancia crea un ráster de salida en el que a cada celda se le asigna el coste acumulativo a la celda de origen más cercana. El algoritmo utiliza la representación de celda de nodo/vínculo utilizada en la teoría de gráficos. En la representación de nodo/vínculo, cada centro de celda se considera un nodo y cada nodo se conecta a los nodos adyacentes mediante varios vínculos.

Cada vínculo tiene una impedancia asociada. La impedancia se deriva de los costes asociados con las celdas en cada extremo del vínculo (desde la superficie de coste) y desde la dirección del movimiento a través de las celdas.

El coste asignado a cada celda representa la distancia de coste por unidad para moverse a través de la celda. El valor final por celda es el tamaño de celda multiplicado por el valor del coste. Por ejemplo, si el ráster de costes tiene un tamaño de celda de 30, y una celda determinada tiene un valor de coste de 10, el coste final de esa celda es 300 unidades.

Costes del viaje entre nodos

El coste de viajar de un nodo al siguiente depende de la orientación espacial de los nodos. La forma en que están conectadas las celdas también afecta el coste del viaje.

Coste del nodo adyacente

Cuando se mueve desde una celda hasta uno de sus cuatro elementos próximos directamente conectados, el coste para moverse a través de los vínculos hasta el nodo vecino es 1 por la celda 1, más la celda 2, dividido por 2:

 a1 = (cost1 + cost2) / 2
  • donde:

    cost1: el coste de la celda 1

    cost2: el coste de la celda 2

    a1: el coste total del vínculo desde la celda 1 a la celda 2

Cómputo del coste para celdas adyacentes

Coste perpendicular acumulativo

El coste acumulativo se determina mediante la siguiente fórmula:

 accum_cost = a1 + (cost2 + cost3) / 2
  • donde:

    cost2: el coste de la celda 2

    cost3: el coste de la celda 3

    a2: el coste de moverse desde la celda 2 a la 3

    accum_cost: el coste acumulativo para moverse hasta la celda 3 desde la celda 1

Cómputo del coste para celdas no adyacentes

Coste del nodo diagonal

Si el movimiento es diagonal, el coste para viajar por el vínculo es 1,414214 (o la raíz cuadrada de 2) multiplicado por el coste de la celda 1 más el coste de la celda 2, dividido por 2:

 a1 = 1.414214 (cost3 + cost2) / 2

Cómputo del coste para celdas diagonales

Cuando se determina el coste acumulativo para el movimiento diagonal, se debe utilizar la siguiente fórmula:

 accum_cost = a1 + 1.414214(cost2 + cost3) / 2

Lista de celdas de coste acumulativo

La creación de un ráster de coste-distancia acumulativo mediante la teoría de grafos se puede visualizar como un intento de identificar la celda de menor coste y agregarla a una lista de salida. Es un proceso iterativo que comienza con las celdas de origen. El objetivo de cada celda es ser asignada rápidamente al ráster de coste-distancia de salida.

Origen de entrada y rásteres de costes

En la primera iteración, se identifican las celdas de origen y se les asigna 0 debido a que no hay un coste acumulativo para devolverles. A continuación, se activan todos los elementos próximos de la celda de origen, y se asigna un coste a los vínculos entre los nodos de la celda de origen y los nodos de las celdas vecinas utilizando las fórmulas de coste acumulativo mencionadas anteriormente. Cada una de estas celdas vecinas pueden alcanzar un origen; por consiguiente, se pueden elegir o asignar al ráster de costes acumulativos de salida. Para poder asignarlas a un ráster de salida, la celda debe tener la siguiente ruta de menor coste hasta un origen.

Los valores de coste acumulativo se ordenan en una lista desde el menor coste acumulativo hasta el mayor.

Lista de valores de coste acumulativo ordenada

La celda de menor coste se selecciona en la lista de celdas de coste acumulativo activa, y el valor para esa ubicación de celda se asigna al ráster de coste de distancia de salida. La lista de celdas activas se expande para incluir los elementos próximos de la celda elegida, ya que esas celdas ahora tienen una manera de llegar a un origen. Sólo aquellas celdas que puedan alcanzar un origen pueden estar activas en la lista. El coste para moverse hacia estas celdas se calcula con las fórmulas de coste acumulativo.

Procesamiento de la lista de valores de coste acumulativo

Nuevamente, se elige la celda activa en la lista con el coste más bajo, se expande la vecindad, se calculan los nuevos costes y se agregan las nuevas celdas de costes a la lista activa.

No es necesario que las celdas de origen estén conectadas. Todos los orígenes desconectados contribuyen de igual manera a la lista activa. Sólo se elige y expande la celda con el menor coste acumulativo, sin importar el origen a la que se asignará.

Procesamiento de la lista de valores de coste acumulativo

Este proceso de asignación continúa. Además, las celdas en la lista activa se actualizan si se crea una ruta nueva y de menor coste mediante la adición de las nuevas ubicaciones de celda al ráster de salida.

Procesamiento de la lista de valores de coste acumulativo

Esta actualización puede ocurrir con la llegada de nuevas rutas para las celdas en la lista activa a medida que se asignan más celdas al ráster de salida. Cuando la celda con el menor valor en la lista de coste acumulativo activa se asigna al ráster de salida, se calculan todos los costes acumulativos. Estos costes también se calculan para las celdas vecinas de la celda de salida recién asignada, incluso si las celdas vecinas están en la lista activa hacia otra celda. Si el nuevo coste acumulativo para las ubicaciones en la lista activa es mayor que el coste que las celdas ya poseen, se ignora el valor. Si el coste acumulativo es menor, el coste acumulativo anterior para la ubicación se reemplaza en la lista activa por el nuevo valor. Esa celda, que ahora tiene acceso a una ruta menos costosa y más conveniente hacia un origen, se mueve hacia la parte superior de la lista activa elegida.

En el ejemplo anterior, la ubicación de la celda en la fila 3, columna 1 (resaltada en el cuadro), tenía un coste acumulativo de 11,0 cuando se colocó en la lista activa para llegar al origen en la parte superior del ráster. Sin embargo, debido a que el origen inferior se expandió hacia esta ubicación, la celda tenía acceso a una ruta de coste acumulativo menos costoso para llegar al origen. El valor para la ubicación se actualizó en la lista activa y se asignó a la salida anterior debido a este coste acumulativo menor.

Procesamiento de la lista de valores de coste acumulativo

Si hay varias zonas o conjuntos de celdas de origen desconectados en el ráster de origen de entrada, el proceso continúa y asigna la celda de menor coste de la lista activa sin importar su origen.

Procesamiento de la lista de valores de coste acumulativo

Cuando los frentes de crecimiento se encuentran, la ruta de menor coste que vuelve al origen procede hasta que todas las celdas elegibles reciban un valor de coste.

Procesamiento de la lista de valores de coste acumulativo

Es concebible pensar que cuando los patrones de crecimiento se encuentran, las celdas del patrón de crecimiento podrán llegar a la celda de origen en otro conjunto o patrón de crecimiento de menor coste; de ser así, se reasignarán al nuevo origen. Este comportamiento se muestra en la celda en la fila 3, columna 1, mencionada anteriormente, pero también está ejemplificada por la celda ubicada en la fila 3, columna 6.

Procesamiento de la lista de valores de coste acumulativo
Procesamiento de la lista de valores de coste acumulativo

Cuando se eligen todas las celdas en la lista activa, el resultado es el coste acumulativo o el ráster de distancia con coste ponderado. El procedimiento utilizado garantiza que cada celda tenga el menor coste acumulativo. Este proceso continúa para todas las celdas hasta que se llega al borde del ráster, se encuentra el límite de la ventana o se alcanza la distancia máxima.

No se permiten viajes a través de las celdas que contengan valores NoData. El menor coste acumulativo para las celdas en la parte trasera de un grupo de celdas NoData se determina mediante el coste de viaje alrededor de estas ubicaciones. Si a una ubicación de celda se le asignan valores NoData en el ráster de costes de entrada, se asignarán valores NoData a la ubicación de celda en el ráster de coste de distancia de salida.

Valores de salida de coste de distancia
Valores de salida de coste de distancia

Temas relacionados


7/11/2012