A method for finding a least-cost wide path in raster space.
Saved in:
| Title: | A method for finding a least-cost wide path in raster space. |
|---|---|
| Authors: | Shirabe, Takeshi1 (AUTHOR) shirabe@kth.se |
| Source: | International Journal of Geographical Information Science. Aug2016, Vol. 30 Issue 8, p1469-1485. 17p. |
| Subjects: | Bit-mapped graphics, Computer graphics research, Digital image processing, Data modeling, Computer simulation |
| Abstract: | Given a grid of cells each having an associated cost value, a raster version of the least-cost path problem seeks a sequence of cells connecting two specified cells such that its total accumulated cost is minimized. Identifying least-cost paths is one of the most basic functions of raster-based geographic information systems. Existing algorithms are useful if the path width is assumed to be zero or negligible compared to the cell size. This assumption, however, may not be valid in many real-world applications ranging from wildlife corridor planning to highway alignment. This paper presents a method to solve a raster-based least-cost path problem whose solution is a path having a specified width in terms of Euclidean distance (rather than by number of cells). Assuming that all cell values are positive, it does so by transforming the given grid into a graph such that each node represents a neighborhood of a certain form determined by the specified path width, and each arc represents a possible transition from one neighborhood to another. An existing shortest path algorithm is then applied to the graph. This method is highly efficient, as the number of nodes in the transformed graph is not more than the number of cells in the given grid and decreases with the specified path width. However, a shortcoming of this method is the possibility of generating a self-intersecting path which occurs only when the given grid has an extremely skewed distribution of cost values. [ABSTRACT FROM PUBLISHER] |
| Copyright of International Journal of Geographical Information Science is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | Given a grid of cells each having an associated cost value, a raster version of the least-cost path problem seeks a sequence of cells connecting two specified cells such that its total accumulated cost is minimized. Identifying least-cost paths is one of the most basic functions of raster-based geographic information systems. Existing algorithms are useful if the path width is assumed to be zero or negligible compared to the cell size. This assumption, however, may not be valid in many real-world applications ranging from wildlife corridor planning to highway alignment. This paper presents a method to solve a raster-based least-cost path problem whose solution is a path having a specified width in terms of Euclidean distance (rather than by number of cells). Assuming that all cell values are positive, it does so by transforming the given grid into a graph such that each node represents a neighborhood of a certain form determined by the specified path width, and each arc represents a possible transition from one neighborhood to another. An existing shortest path algorithm is then applied to the graph. This method is highly efficient, as the number of nodes in the transformed graph is not more than the number of cells in the given grid and decreases with the specified path width. However, a shortcoming of this method is the possibility of generating a self-intersecting path which occurs only when the given grid has an extremely skewed distribution of cost values. [ABSTRACT FROM PUBLISHER] |
|---|---|
| ISSN: | 13658816 |
| DOI: | 10.1080/13658816.2015.1124435 |
