GIS

GIS
Students Supported

Jeremy Fishman '09

Improved Visibility Computation on Massive Grid Terrains

Jeremy Fishman '09We 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].

Jeremy Fishman '09 A radial sweep in sectors sweep Jeremy Fishman '09 A radial sweep in bands
Jeremy Fishman '09 The SRTM1 region definition"
(From ftp://e0srp01u. ecs.nasa .gov/srtm/}		 Jeremy Fishman '09 The viewpoint of a point on a terrain is shown in white.