An efficient multiple scanning order algorithm for accumulative least-cost surface calculation

doi:10.1080/13658816.2022.2052885

An efficient multiple scanning order algorithm for accumulative least-cost surface calculation

2022-03-24

2

PRE

AI

DOI：10.1080/13658816.2022.2052885

Original

Original request for help

Save

Abstract

En 中文

The least-cost surface (LCS) calculation is a compute-intensive problem conventionally solved by the queue-based Dijkstra's algorithm. Alternative raster-based scanning algorithms have also been proposed which use a moving window to scan the whole study area iteratively. Here we propose improvements to the raster-based algorithms. The main improvement is to implement multiple scanning orders (MSO) to replace the conventional single scanning order (SSO, typically from upper-left corner to lower-right corner, row by row). We compared the performance of different algorithms over different cost surfaces and with different numbers of source points. The comparison shows that a raster-based algorithm adopting MSO has a substantially better performance than a conventional raster-based algorithm using SSO. An MSO raster-based algorithm is generally comparable to the queue-based Dijkstra's algorithm, and surpasses the latter over a relatively simple cost surface (e.g. in which the cost is resampled) and/or when the number of source points is relatively large. Our empirical experiments suggest that MSO reduces the time complexity from to Theta(N-2) to Theta(NlogN). Additionally, we found that the MSO raster-based algorithm can be easily parallelized using shared-memory parallel programming.

Keywords:

Least-cost surface

geocomputation

spatial analysis

An efficient multiple scanning order algorithm for accumulative least-cost surface calculation

Abstract

Journal

Organization