Affordable Access

Computing visibility on terrains in external memory

Authors
Publisher
SIAM
Publication Date
Disciplines
  • Computer Science
  • Design
  • Mathematics

Abstract

Computing Visibility on Terrains in External Memory Herman Haverkort∗ Laura Toma† Yi Zhuang‡ Abstract We describe a novel application of the distribution sweeping technique to computing visibility on terrains. Given an arbi- trary viewpoint v, the basic problem we address is computing the visibility map or viewshed of v, which is the set of points in the terrain that are visible from v. We give the first I/O- efficient algorithm to compute the viewshed of v on a grid terrain in external memory. Our algorithm is based on Van Kreveld’s O(n lgn) time algorithm for the same problem in internal memory. It uses O(sort(n)) I/Os, where sort(n) is the complexity of sorting n items of data in the I/O-model. We present an implementation and experimental evaluation of the algorithm. Our implementation clearly outperforms the previous (in-memory) algorithms and can compute visi- bility for terrains of up to 4GB in a few hours on a low-cost machine. 1 Introduction In this paper we consider the problem of computing visibility on very large terrains in external memory. Given an arbitrary viewpoint v and a terrain, the basic problem we address is computing the visibility map or viewshed of v, which is the set of points in the terrain that are visible from v (Figure 1). Visibility has applications in graphics and game design, and mainly in Geographic Information Systems (GIS), ranging from path planning, navigation, landscaping, to placement of fire towers, radar sites and cellphone towers [12, 16]. Visibility has been widely studied in computational geometry and graphics; for a survey of the various problems and results see Cole and Sharir [9] or De Floriani and Magillo [11]. Recently, researchers have obtained a number of results on visibility addressing the watchtower problem and terrain guarding [2, 8]. The standard terrain model used in geometry is the polyhedral terrain, which is a continuous piecewise linear function defined over the triangles of a triangulation in

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Visibility problems for polyhedral terrains

on Journal of Symbolic Computatio... Jan 01, 1989

Computing Large Planar Regions in Terrains

on Electronic Notes in Theoretica... Jan 01, 2001

A fuzzy approach to visibility maps creation over...

on Fuzzy Sets and Systems Jan 01, 2003
More articles like this..