Abstract
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 to
Additionally, we found that the MSO raster-based algorithm can be easily parallelized using shared-memory parallel programming.
Acknowledgement
We sincerely thank the valuable contributions given by the editor (Professor Shawn Laffan) and the anonymous reviewers.
Data and codes availability statement
The relevant datasets of this study are archived in the zenodo site (https://zenodo.org/record/6339694#.Yif6u3rMKUl).
Disclosure statement
No potential conflict of interest was reported by the author(s).
Additional information
Notes on contributors
Yuanzhi Yao
Yuanzhi Yao is a postdoctoral research fellow at the College of Forestry and Wildlife Sciences, Auburn University and a research professor at the School of Geographic Sciences, East China Normal University. He develops hydrological, and water quality components of terrestrial ecosystem model and disseminates research results on climatic and anthropogenic influences on the physical and biogeochemical processes within the inland water ecosystem and the associate greenhouse gas emissions.
Xun Shi
Xun Shi is a professor at the Department of Geography, Dartmouth College. His specialty is in geographic information systems (GIS), quantitative spatial analysis and modeling, and the geocomputational approach. He has explored the applications of GI technologies in various domains, particularly in health studies, digital soil mapping, urban and regional planning, public participation, and renewable energy studies.
Zekun Wang
Zekun Wang received his Ph.D degree (2022) at the Department of Mechanical Engineering, Auburn University. He mainly engaged in the application of machine learning methods in image processing. He also concerns about the energy usage and reliability of electrical device, and whisker growing behavior and suppression under extreme environment.