Optimization Online


The viewshed problem: a theoretical analysis and a new algorithm for finding the viewshed of a given point on a triangulated terrain

HALUK ELİŞ(helis***at***bilkent.edu.tr)
BARBAROS TANSEL(barbaros***at***bilkent.edu.tr)
OSMAN OĞUZ(ooguz***at***bilkent.edu.tr)

Abstract: We give a comprehensive theoretical treatment for calculating the viewshed of a given point, present an analytical solution to the viewshed problem and a new algorithm for finding the viewshed on a triangulated terrain. We implement our algorithm on a real terrain. Some algorithms make use of the horizon information of the terrain to calculate viewshed. The vertices of the horizon of the terrain are projected onto the supporting plane of the triangle of interest to find the visible region on the triangle. We show that this approach is erroneous. We offer an alternative model in which we project relevant triangles of the terrain onto the triangle of interest. It is shown that the invisible region on a given triangle caused by another triangle is characterized by a nonlinear system of equations, for which a closed-form solution is given. Our analytical treatment results in a new exact algorithm which can be used in studies such as optimal placement of guards on terrains where exact viewsheds of guards are needed.

Keywords: viewshed analysis on terrains; projection of a triangle; a polynomial-time viewshed algorithm; an application of polyhedral theory

Category 1: Other Topics (Other )

Citation: Bilkent University, 08/2013

Download: [PDF]

Entry Submitted: 08/26/2013
Entry Accepted: 08/26/2013
Entry Last Modified: 08/26/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society