Algoritmo de acumulação de distância

Disponível com Image Server

As ferramentas Acumulação de distância e Alocação de distância substituem as ferramentas de distância de custo herdadas. Essas novas ferramentas medem a distância de custo em todas as direções, reconstruindo uma superfície acumulativa contínua, em vez de encontrar caminhos através de uma rede de centros de células Você pode criar superfícies de custo acumulativo de saída a partir de superfícies de fricção de custo de entrada e outros parâmetros. Assim como em outras superfícies, você pode obter uma compreensão mais precisa dos resultados adicionando linhas de curva de nível (linhas de custo acumulativo igual), visualizando-as em 3D e visualizando-as em combinação com vertentes de alocação. Normalmente, o objetivo de construir essa superfície é traçar caminhos de menor custo, que são caminhos de descida mais íngreme.

Superfície de custo acumulativo

O algoritmo usado por essas ferramentas reconstrói uma superfície a partir de sua declividade.

Abordagem de reconstrução de superfície

Com as ferramentas Acumulação de distância e Alocação de Distância, encontrar o menor custo acumulativo não é mais um problema de rede. O raster de custo acumulativo de saída é uma superfície com uma forma desconhecida. Você deseja descobrir a forma dada apenas sua declividade em cada célula na área de estudo. Essa abordagem usa conceitos de geometria diferencial para calcular a distância real e os custos em todas as direções.

A superfície de custo acumulativo responde a três questões importantes:

• Onde o custo aumenta rapidamente em função da distância?
• Quais células de origem estão mais próximas de uma determinada célula não-fonte?
• Qual caminho deve ser seguido de uma célula sem origem até a célula de origem mais próxima?

Você pode usar visualizações 3D e linhas de curva de nível com a superfície de saída para encontrar as respostas para essas perguntas. Você pode usar as ferramentas Alocação de Distância e Caminho Favorável como Linha para obter respostas mais precisas.

As subseções abaixo descrevem a relação entre uma superfície de atrito de custo de entrada simples e a superfície de custo acumulativo de saída.

Superfície de atrito de custo de entrada simples

Considere um raster de fricção de custo simples que tem uma seção central com custo = 3, uma seção intermediária com custo = 2 e uma seção externa com custo = 1.

Uma entrada raster de fricção de custo como anéis concêntricos com um ponto indicando o centro é mostrada.

A interpretação 3D pode ser usada para entender a relação entre o raster de atrito de custo e a superfície de custo acumulativo de saída. A altura h da superfície na célula c é a soma das inclinações do raster de custo de entrada multiplicada pelas distâncias nas quais essas declividades estão ativas (h = 3 * d1 + 2 * d2 + 1 * d3).

A relação entre a entrada de atrito de custo e a superfície de custo acumulativo de saída é mostrada em uma representação 3D.

Uma visualização plana da mesma superfície de saída mostra como as linhas de curva de nível representam a mudança de custo acumulativo. Os valores de declividade e aspecto na localização da célula c também são mostrados. Aspecto (a direção da descida mais íngreme) está sempre em ângulos retos com a linha de curva de nível.

As linhas de de curva de nível mostram como o custo acumulativo muda em uma visualização plana da superfície raster.

Incorporar o menor custo acumulativo

Um caso um pouco mais complicado é mostrado abaixo. O custo acumulativo (elevação) em uma célula sem fonte virá da fonte que chega àquela célula com o menor custo.

O raster de custo tem dois valores: 1 como cinza claro e 3 como cinza escuro. Os pontos de origem são S1 e S2. A célula D sem origem está mais próxima de S1 em termos de custo acumulativo.

Um raster de custo de entrada é sobreposto por pontos de origem de entrada e uma célula de origem.

Adicionar linhas de curva de nível à superfície de custo acumulativo pode ajudá-lo a visualizar a rapidez com que o custo muda à medida que você se afasta das fontes. Começando no local sem origem e movendo-se em ângulos retos para as linhas de curva de nível, você viaja de volta para a célula de origem mais próxima. O caminho não vai para a fonte geometricamente mais próxima devido ao alto custo em torno dessa fonte.

Uma visualização plana da superfície de custo menos acumulativo para duas fontes (S1 e S2) de um local sem fonte é mostrada.

Uma visualização 3D mostrando a mesma superfície de custo acumulativo mínimo está abaixo. A superfície é muito mais íngreme em torno da fonte cara (o custo se acumula mais rapidamente). Essa fonte possui a superfície de custo mínimo apenas muito próxima a ela. Em todas as outras células da área de estudo, a superfície pertence à fonte à esquerda.

Uma visualização em perspectiva 3D de uma superfície de custo acumulativo mínimo para duas fontes é mostrada.

Regiões de alocação como vertentes

À medida que a superfície de fricção de custo de entrada e a superfície de custo acumulativo de saída se tornam mais complicadas, você ainda pode usar linhas de curva de nível, declividade e aspecto para entender o comportamento das superfícies de custo acumulativo. Além disso, as regiões de alocação em torno das fontes funcionam como divisores de águas na superfície de saída do custo acumulativo. Todos os caminhos de menor custo dentro de uma região de alocação fluem para a mesma origem. As vertentes de alocação são combinadas com linhas de curva de níveis e uma visualização 3D nos exemplos abaixo.

Superfícies de custo acumulativo mais complicadas, como esta superfície de tempo de viagem, podem ser visualizadas precisamente em 2D e 3D usando linhas de curva de níveis (isocronas neste caso).

Uma superfície de custo acumulativo com linhas de curva de nível em uma visualização plana 2D é mostrada.

Uma visualização 3D da mesma superfície é mostrada na imagem a seguir. As falésias ao fundo são barreiras causadas pela presença de um rio.

Uma visualização em perspectiva 3D de uma superfície de custo acumulativo é mostrada.

Os caminhos de menor custo fluem pela superfície de custo acumulativo em direção à fonte que define a zona de alocação (divisor de águas), conforme mostrado na imagem a seguir:

Uma visualização em perspectiva 3D do fluxo de caminhos de menor custo na superfície de custo acumulativo é mostrada.

O algoritmo de reconstrução de superfície é uma extensão do algoritmo de rede

Para encontrar uma superfície de custo acumulativo usando apenas o conhecimento do valor de declividade mais íngreme em cada célula, você também pode usar o algoritmo de reconstrução de superfície. Esse algoritmo é semelhante ao algoritmo de caminho mais curto usado pelas ferramentas de distância de custo herdadas, mas com uma etapa extra para fornecer uma aproximação de custo acumulativo que não segue uma das oito direções de rede. Isso é chamado de passo Eikonal. Segue uma breve descrição e mais detalhes podem ser encontrados em Sethian, 1999.

Para entender esta etapa no contexto, você encontrará o custo acumulativo z5 para a célula central abaixo. Suponha que você conheça todos os custos acumulativos vizinhos zi. Além disso, a partir do raster de custo de entrada, você conhece o valor de declividade S na célula central.

Figura 4. O algoritmo de reconstrução de superfície calcula uma altura z5 para a célula central fazendo várias aproximações para essa altura usando a declividade do raster de fricção de custo de entrada na célula central, juntamente com as alturas conhecidas assumidas zi para as células vizinhas.

Por exemplo, uma aproximação para z5 pode ser ao longo da diagonal entre z3 e z5, onde z5 = z3 + 1.4 * tamanho da célula * S, como mostrado na figura abaixo. Nesse caso, S—o valor do raster de custo de entrada—é interpretado como a declividade do triângulo abc. Para todas essas aproximações de estilo de rede, apenas a declividade em z5 é usada para aproximar o custo acumulativo em z5. Isso é diferente do algoritmo de rede legado, que usa uma média de custos de pares de células.

Figura 5. Um cálculo de passo diagonal é mostrado. A declividade s da superfície de atrito de custo de entrada é interpretada como a declividade da hipotenusa do triângulo abc.

Oito aproximações de rede podem ser feitas, incluindo quatro que usam pares de alturas existentes, conforme mostrado na sequência de três figuras abaixo. Nesse caso, o valor do raster de custo de entrada na localização da célula z5 é interpretado como a magnitude S do gradiente do plano que passa pelos dois pontos conhecidos e a elevação desconhecida z5. A partir dessa relação, você pode resolver para z5. Este é o passo Eikonal.

Figura 6. Entradas de passos Eikonais são mostradas: duas alturas, z6 e z8, são conhecidas.

A magnitude do gradiente do plano é calculada.

Figura 7. A medida S do raster de custo é a magnitude do gradiente do plano que passa pelas duas elevações conhecidas z8 e z6 e a elevação desconhecida z5

A direção do gradiente é calculada.

Figura 8. A direção do gradiente é o valor de aspecto (direção para trás) para a célula z5.

A etapa Eikonal também recupera a informação de aspecto em z5, que é chamada de direção de retorno.

Existem agora doze aproximações para a elevação na célula central. O mínimo deles é selecionado e registrado como valor de custo acumulativo z5 para a célula central. Se você solicitou um raster de direção inversa, o aspecto do gradiente (conforme descrito no parágrafo anterior) é registrado no local correspondente no raster de direção inversa de saída.

Se você solicitou um raster de direção inversa, o aspecto do gradiente (conforme descrito no parágrafo anterior) é registrado no local correspondente no raster de direção inversa de saída. Eventualmente, os valores de elevação param de mudar e o algoritmo termina. As elevações iniciais são fornecidas pelas fontes: elas são zero ou o valor de acumulação inicial por fonte. Os outros valores iniciais de elevação são definidos como infinito. Os detalhes são descritos em Sethian (1999). A implementação da Esri disso é uma combinação de técnicas descritas em Sethian (1999) e Zhao (2004).

Em resumo, a partir da declividade de cada célula, essas etapas reconstroem a elevação da superfície de custo acumulativo e a direção da descida mais íngreme.

Caminhos de menor custo

Os caminhos de menor custo seguem a direção descendente mais íngreme sobre a superfície de custo acumulativo. Essa direção, para uma célula, é mostrada acima na figura 8. O raster de direção inversa de saída armazena essa direção para cada célula. Você pode usar a ferramenta Caminho Favorável como Linha, com o raster de direção traseira como uma entrada, para traçar esses caminhos a partir de qualquer célula não-fonte.

Nas figuras abaixo, um caminho curvo de menor custo é mostrado a partir da célula azul sem origem d no canto superior direito e viajando para a célula de origem inferior s. Enquanto d está geometricamente mais próximo da fonte superior, devido ao alto custo em torno dessa fonte, é mais barato viajar até s seguindo o caminho curvo.

O destino d é o quadrado azul. Ele viaja por uma área de menor custo até a fonte que pode alcançar de forma mais barata, contornando a fonte de alto custo para fazê-lo.

Figura 9. A construção de caminhos de menor custo usando uma superfície de custo acumulativo construída a partir da superfície de fricção de custo de entrada da Figura 3 é mostrada.

Embora possa parecer que o nome não é intuitivo, os locais de entrada para a construção do caminho de menor custo são chamados de destinos. As fontes foram usadas para construir a superfície e são os locais onde terminam os caminhos de menor custo.

As zonas de alocação em torno das origens esclarecem ainda mais que o caminho de menor custo do destino viajará para a origem inferior e não para a origem superior. Em seguida, a área selecionada será ampliada para mostrar como os valores das células no raster de direção traseira são interpretados.

A localização da área de estudo é marcada pela caixa.

A treliça conectando os centros das células de direção traseira é mostrada em cinza escuro. Os limites das células são mostrados em cinza claro e os valores das células são mostrados como setas de azimute. À medida que o caminho de menor custo cruza as linhas da rede, ele usa o azimute na célula de direção traseira mais próxima na direção da viagem para atualizar sua direção. No vértice do caminho superior próximo à célula a, o valor da direção de retorno armazenado em a será usado para direcionar a linha que sai desse vértice. A próxima linha de treliça a ser cruzada é a mais próxima da célula b, de modo que o azimute será usado para sair do segundo vértice e assim por diante.

Grade de treliça de valores de células do raster de direção traseira

Em resumo, os caminhos de menor custo começam e terminam nos centros das células. Outros vértices de caminho podem estar em qualquer lugar na rede de linhas horizontais e verticais que passam pelos centros das células.

Cálculo de declividade efetiva

Os valores de declividade descritos na seção anterior não vêm estritamente do raster de fricção de custo de entrada. Existem várias outras entradas que, juntas, determinam a declividade efetiva usada pelo algoritmo de reconstrução de superfície. Uma descrição detalhada dessas entradas, incluindo a importância de contabilizar a direção do movimento através de uma célula e a direção do deslocamento de ou para uma fonte, é apresentada em outros tópicos. Aqui, o foco está em como as entradas são usadas pelo algoritmo de reconstrução de superfície. As entradas são as seguintes:

• A entrada de fricção de custo, C
• A entrada de superfície, S
• O multiplicador de custo de origem, M
• A função de fator horizontal, HF
• A função de fator vertical, VF

A declividade efetiva usada pelo algoritmo de reconstrução tem esta forma geral:

Declividade efetiva = C * S * M * HF * VF

Esse valor é então multiplicado pelo tamanho da célula ou sqrt(2) * tamanho da célula e adicionado a uma altura existente para obter uma das estimativas de altura da direção da rede. Uma função mais complicada de declividade efetiva é usada para obter uma estimativa de altura para o passo Eikonal.

A declividade efetiva deve ter unidades de custo acumulativo divididas pela distância linear, uma taxa. Por exemplo, se a superfície de custo acumulativo for medir o tempo de viagem em horas e o tamanho da célula de análise for em metros, a declividade efetiva deverá ter unidades de horas/metro.

Como a declividade efetiva é um produto de vários termos, você deve garantir que as unidades dos termos individuais se combinem para produzir as unidades corretas de declividade efetiva. Por exemplo, se você estiver usando apenas um raster de fricção de custo simples para descrever o tempo de viagem independente da direção, seus valores de célula raster de fricção de custo devem ter unidades de horas/metro. Alternativamente, se você também estiver usando a função de caminhada de Tobler como sua função de fator vertical, essa função de caminhada terá unidades de horas/metro e sua superfície de fricção de custo, se presente, deve ser interpretada como um peso sem unidade. Você deve então garantir que seus valores de célula de fricção de custo possam ser interpretados dessa maneira. Em outras palavras, sua função vertical e fricção de custo não podem ser taxas.

Você não controla diretamente a entrada de superfície (S). É um peso sem unidade que estica o tamanho da célula para cobrir a distância real da superfície 3D entre os centros das células. Na Figura 2, o algoritmo de reconstrução de superfície calcula uma altura z5 para a célula central fazendo várias aproximações para essa altura usando a declividade do raster de fricção de custo de entrada na célula central, juntamente com as alturas conhecidas assumidas para as células vizinhas.

As barreiras são conectadas por extremidades

Barreiras nas ferramentas Acumulação de distância e Alocação de Distância são células de entrada que não podem ser passadas. Eles são representados como células NoData durante a computação. Eles são apresentados explicitamente como um parâmetro de ferramenta ou implicitamente como valores NoData em uma das outras entradas de raster (como o raster de fricção de custo). No primeiro caso, eles são rasterizados e transformados em NoData no raster de custo. Como o algoritmo de reconstrução de superfície não pode diminuir a estimativa de altura para uma célula de barreira, ele encontrará uma maneira de contorná-la.

O algoritmo de reconstrução de superfície usa todos os oito vizinhos de uma célula para encontrar sua estimativa de altura. Vizinhos de barreira conectados por canto não impedirão que um vizinho diagonal seja usado para obter uma estimativa de altura. Na imagem abaixo, uma estimativa de altura para z5 pode ser obtida a partir de z3, mesmo que as células z2 e z6 sejam barreiras.

Se z2 e z6 fossem destinados a fazer parte de uma feição de barreira linear, como um canal ou rio, esse comportamento anularia a intenção da barreira. Para evitar isso, o algoritmo de reconstrução de superfície favorece a conexão de células de barreira sobre a conexão de células não-barreira. Isso significa que células NoData adicionais são introduzidas no raster de custo para garantir que todas as células de barreiras existentes compartilhem uma extremidade. Na imagem acima, a célula z5 ou a célula z3 também se tornaria uma célula de barreira.

Ao usar barreiras em sua análise, considere esse comportamento e ajuste o tamanho da célula de análise de forma que a conectividade pretendida em torno das barreiras seja preservada. Você pode usar a ferramenta Estatísticas focais engrossar versões raster de feições lineares para usá-los como barreiras ou como redes lineares, que não devem ser interrompidas por células de barreira adjacentes.

Referências

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, No. 3, DOI: 10.3138/D327-0323-2JUT-016M

Goodchild, M.F. "Uma avaliação de soluções em treliça para o problema de localização de corredores", Ambiente e Planeamento A: Economia e Espaço, 1977, vol. 9, páginas 727-738

Sethian, J.A. Métodos de definição de nível e marcha rápida (Interfaces em evolução em geometria computacional, mecânica dos fluidos, visão computacional e ciência dos materiais) 2ª edição, Cambridge University Press, 2ª edição (1 de junho de 1999)

Warntz, W. "Transporte, Física Social e a Lei da Refração",O Geógrafo Profissional, 1957, Vol. 9, No. 4, pp. 2-7.

Zhao, H. "Um método de varredura rápida para equações Eikonais", Mathematics off Computation, 2004, Vol. 74, No, 250, páginas 603-627