An Output Sensitive Algorithm for Computing Viewsheds and Total Viewsheds on 2D Terrains

Modeling and computing visibility on terrains has useful applications in many fields. The most common visibility-related concepts on terrains are the viewshed and total viewshed. The viewshed of a point v in a terrain is the area in the terrain that is visible from v. The total viewshed is a surface which, at point v, has a value equal to the size of the viewshed of v. In many applications, it is desirable to model a terrain and its corresponding viewshed and total viewshed with a high level of accuracy. This is possible due to widely available high-resolution terrain data collected using LiDAR technology. In order to compute viewsheds and total viewsheds on large high-resolution datasets, efficient algorithms are necessary. The only known method for computing the total viewshed is to compute the viewshed for each point in the terrain, which is too slow in practice as it can take on the order of days or more for large terrains. In this thesis, we present a new output sensitive algorithm for computing viewsheds and total viewsheds on grid terrains, which is based on a multi-resolution approach. First, we compute the viewshed on a smaller low-resolution grid terrain consisting of blocks of points, which is guaranteed to be a superset of the ground-truth viewshed. Second, we refine the low-resolution viewshed to get the exact ground-truth viewshed. On a grid terrain of n points, our algorithm runs in O( n/k log n/k + v log n), where k is the block size and v is the size of the low-resolution viewshed. In practice, our algorithm runs over 20 times faster than the previously fastest algorithm on large high-resolution grid terrains