Jeremy Fishman '09
Improved Visibility Computation on Massive Grid Terrains
We have developed two new algorithms for computing viewsheds (visibility maps) on massive grid terrains. Given a terrain T, specified by the elevation of points in a regular grid, and given a viewpoint v, the viewshed (visibility map) of v is the set of grid points of T that are visible from v. Our algorithms "sweep" the terrain by rotating a ray around the viewpoint while maintaining the terrain profile along the ray. To interpolate terrain height at points along the ray, we use a nearest-neighbor interpolation of the grid. The difference between the two algorithms is in the preprocessing before the sweep: the first algorithm sorts the grid points into concentric bands around the viewpoint, while the second algorithm sorts the grid points into sectors around the viewpoint. On a terrain of n grid points, these algorithms run in O(n lg n) time and O(sort(n)) IOs in the IO-model of Agarwal and Vitter.
We tested our algorithms on NASA SRTM data, and found that the faster of our new algorithms computes the viewshed of a terrain of 7.6 billion points (28.4 GiB) in 430 minutes on a machine with .5 GB RAM and a laptop-speed hard drive. This is an order of magnitude faster than the algorithm from our previous work.
Paper: Improved visibility computation on massive grid terrains, in Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in geographic Information Systems (ACM SIGSPATIAL GIS 2009). [pdf].
|A radial sweep in sectors sweep||A radial sweep in bands|
|The SRTM1 region definition"
(From ftp://e0srp01u. ecs.nasa .gov/srtm/}
|The viewpoint of a point on a terrain is shown in white.|