An Efficient External Memory Algorithm for Terrain Viewshed Computation
| Autor: | Marcus V. A. Andrade, Chaulio R. Ferreira, Salles V. G. Magalhães, W. Randolph Franklin |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Source code
Computer science media_common.quotation_subject Computation 0211 other engineering and technologies Terrain 02 engineering and technology Data structure Computer Science Applications Viewshed analysis 020204 information systems Modeling and Simulation Computer graphics (images) Signal Processing 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Out-of-core algorithm Geometry and Topology Cache Algorithm Auxiliary memory 021101 geological & geomatics engineering Information Systems media_common |
| Zdroj: | ACM Transactions on Spatial Algorithms and Systems. 2:1-17 |
| ISSN: | 2374-0361 2374-0353 |
| DOI: | 10.1145/2903206 |
| Popis: | This article presents T iled VS, a fast external algorithm and implementation for computing viewsheds. T iled VS is intended for terrains that are too large for internal memory, even more than 100,000×100,000 points. It subdivides the terrain into tiles that are stored compressed on disk and then paged into memory with a custom cache data structure and least recently used algorithm. If there is sufficient available memory to store a whole row of tiles, which is easy, then this specialized data management is faster than relying on the operating system’s virtual memory management. Applications of viewshed computation include siting radio transmitters, surveillance, and visual environmental impact measurement. T iled VS runs a rotating line of sight from the observer to points on the region boundary. For each boundary point, it computes the visibility of all terrain points close to the line of sight. The running time is linear in the number of points. No terrain tile is read more than twice. T iled VS is very fast, for instance, processing a 104,000×104,000 terrain on a modest computer with only 512MB of RAM took only 1½ hours. On large datasets, T iled VS was several times faster than competing algorithms, such as the ones included in GRASS. The source code of T iled VS is freely available for nonprofit researchers to study, use, and extend. A preliminary version of this algorithm appeared in a four-page ACM SIGSPATIAL GIS 2012 conference paper, “More Efficient Terrain Viewshed Computation on Massive Datasets Using External Memory.” This more detailed version adds the fast lossless compression stage that reduces the time by 30% to 40%, and many more experiments and comparisons. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|