A view-tree method to compute viewsheds from digital elevation models

Viewshed computation is a central component for visibility analysis. The majority of existing viewshed computation methods use regular square grid digital elevation models (DEMs) and have limitations in considering spatial relationships among observers, targets, and line-of-sight (LOS). Therefore, considering that the visibility is dominated by LOS between observers and targets, this study proposes a method to compute viewsheds using a new type of tree structure, the “view-tree,” that can efficiently extract LOS from DEMs for viewshed computation. The proposed method first constructs a view-tree using cells in regular square grid DEM according to the spatial occlusion relationships among cells. Then, the method traverses the view-tree to judge the visibility of each tree node and derives the viewshed. The results show that the view-tree method is 40% faster than the traditional R2 method. The view-tree method also reduces the error and omission rates by approximately 60% compared with the popular XDraw method.