Algorithms for Visibility Computation on Terrains: A Survey
Environment and Planning B Planning and DesignPublished 1 October 2003
Leila De Floriani, Paola Magillo
Citations120
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
In this paper, the authors consider a number of visibility problems on terrains and present an overview of algorithms to tackle such problems on triangulated irregular networks and regular square grids.
Abstract
Several environment applications require the computation of visibility information on a terrain. Examples are optimal placement of observation points, line-of-sight communication, and computation of hidden as well as scenic paths. Visibility computations on a terrain may involve either one or many viewpoints, and range from visibility queries (for example, testing whether a given query point is visible), to the computation of structures that encode the visible portions of the surface. In this paper, the authors consider a number of visibility problems on terrains and present an overview of algorithms to tackle such problems on triangulated irregular networks and regular square grids.
Keywords
Computer Science
Mathematics of ComputationComputational Geometry--An Introduction.
4,264 Citations1986Mikhail J. Atallah, Franco P. Preparata +1 more
Computational Geometry
3,606 Citations1985Franco P. Preparata, Michael Ian Shamos
This book clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics and points the way to the solution of the more challenging problems in dimensions higher than two.
SIAM Journal on ComputingOptimal Search in Planar Subdivisions
748 Citations1983David Kirkpatrick
This work presents a practical algorithm for subdivision search that achieves the same (optimal) worst case complexity bounds as the significantly more complex algorithm of Lipton and Tarjan, namely $O(\log n)$ search time with $O(n)$ storage.
Communications of the ACMPlanar point location using persistent search trees
487 Citations1986Neil Sarnak, Robert E. Tarjan
This work develops a persistent form of binary search tree that supports insertions and deletions in the present and queries in the past, and provides an alternative to Chazelle's "hive graph" structure, which has a variety of applications in geometric retrieval.
Vector models for data-parallel computing
464 Citations1990Guy E. Blelloch
A model of parallelism that extends and formalizes the Data-Parallel model on which the Connection Machine and other supercomputers are based is described, and it is argued that data-parallel models are not only practical and can be applied to a surprisingly wide variety of problems, they are also well suited for very-high-level languages and lead to a concise and clear description of algorithms and their complexity.
Information Processing LettersFinding the upper envelope of n line segments in O(n log n) time
267 Citations1989John Hershberger
The method can be used to compute the upper envelope of “segments” that intersect pairwise at most k times and computes theupper envelope in O(λk + 1(n)log n) time.
SIAM Journal on ComputingLocation of a Point in a Planar Subdivision and Its Applications
222 Citations1977D. T. Lee, F. P. Preparata
International Journal of Geographical Information SystemsAlgorithm and implementation uncertainty in viewshed analysis
188 Citations1993Peter Fisher
The study highlights three issues: the need for standards and/or empirical benchmark datasets for GIS functions; the desirability of public data sets used in the design of viewshed algorithms; and the need to understand the motivation behind the selection of algorithms.
Journal of Symbolic ComputationVisibility problems for polyhedral terrains
161 Citations1989Richard Cole, Micha Sharir
An O(n@l"4(n)log n)-time algorithm is presented that preprocesses L and @s into a data-structure of size O(o(log^2n) time ray Shooting queries, which supports fast ray shooting queries.
International Journal of Geographical Information SystemsVisibility graphs and landscape visibility analysis
108 Citations2001David O’Sullivan, Alasdair Turner
An approach to visibility analysis based on the visibility graph is presented, suggesting that measures derived from the visibility graph may be of particular relevance to the growing interest in quantifying the perceptual characteristics of landscapes.
International Journal of Geographical Information SystemsAnalyses of visibility sites on topographic surfaces
105 Citations1991Jay Lee
Five types of site analysis using visibility information are discussed in this paper, including both fixed and variable heights of problems in visibility sites, as a new area of application in geographical information systems.
Environment and Planning B Planning and DesignAn Exploration of Probable Viewsheds in Landscape Planning
92 Citations1995P.F. Fisher
It is shown that the analysis of probable viewsheds gives much more information about the nature of the viewable area, which in turn enables a more thorough approach to planning the use of viewable areas.
Dynamic computational geometry
84 Citations1983Mikhail J. Atallah
This work considers problems in computational geometry when every one of the input points is moving in a prescribed manner and presents and analyze efficient algorithms for a number of problems and proves lower bounds for some of them.
An efficient output-sensitive hidden surface removal algorithm and its parallelization
82 Citations1988John H. Reif, Subhankar Sen
This paper presents an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly like the terrain maps and presents a parallel algorithm based on a similar approach.
IEEE Transactions on Visualization and Computer GraphicsFast horizon computation at all points of a terrain with visibility and shading applications
72 Citations1998A. James Stewart
Experimental and theoretical results are presented which show that the algorithm is more accurate that previous algorithms and is faster than previous algorithms in terrains of more than 100,000 sample points.
Mathematics and visualizationMultiresolution Mesh Representation: Models and Data Structures
68 Citations2002Leila De Floriani, Paola Magillo
A multiresolution mesh provides several alternative mesh-based approximations of a spatial object (e.g., a surface describing the boundary of a solid object, or the graph of a scalar field).
Siting Observers on Terrain
57 Citations2002Wm. Randolph Franklin
An experimental study of a new algorithm that synthesises separate programs, for fast viewshed, and for fast approximate visibility index determination, implemented in a working testbed for siting multiple observers jointly to cover terrain from a full level-1 DEM.
Variations on sweep algorithms: efficient computation of extended viewsheds and class intervals
45 Citations1996Marc van Kreveld
Two novel applications of the plane sweep paradigm are demonstrated, namely, for the computation of extended viewsheds on gridded DEMs and for class interval selection on TIN-based DEMs.
Computers & GeosciencesImplementing an intervisibility analysis model on a parallel computing system
39 Citations1992Kim Mills, Geoffrey Fox +1 more
Results of this study show that intervisibility may be overestimated when the effects of DEM error are ignored, and that data communication is the most important computational issue in this application.
AlgorithmicaOn sorting triangles in a delaunay tessellation
39 Citations1991Leila De Floriani, Bianca Falcidieno +2 more
In a two-dimensional Delaunay-triangulated domain, there exists a partial ordering of the triangles (with respect to a vertex) that is consistent with the two-dimensionally visible triangles from that vertex.
The Visual ComputerHorizon computation on a hierarchical triangulated terrain model
30 Citations1995Leila De Floriani, Paola Magillo
This work considers the horizon computation problem on a hierarchical polyhedral terrain, and describes a method which extracts the terrain edges at a given resolution, and proposes a randomized algorithm for dynamically updating a horizon under insertions and deleting of terain edges.
International Journal of Geographical Information SystemsParallelizing visibility computations on triangulated terrains
23 Citations1994Leila De Floriani, C. Montani +1 more
A parallel algorithm for computing the visible region of an observation point located on the terrain is proposed, based on a sequential triangle-sorting visibility approach proposed by De Floriani et al. (1989).
Efficient hidden surface removal for objects with small union size
20 Citations1991Matthew J. Katz, Mark H. Overmars +1 more
An algorithm that computes the visible portions of a set of n non-intersecting objects in space in time O((U(n)+k)log2n), where U(n') is a super-additive bound on the maximal complexity of the union of (the projections on a viewing plane of) any n' objects from the family under consideration, and k is the complexity ofthe resulting visibility map.
GeoInformaticaVisibility Computations on Hierarchical Triangulated Terrain Models
18 Citations1997Leila De Floriani, Paola Magillo
This paper considers visibility computations on hierarchical terrain models based on triangular subdivisions, called Hierarchical Triangulated Irregular Networks (HTINs), and proposes algorithms for performing such operations on an HTIN at variable resolution.
Lecture notes in computer scienceA simplified technique for hidden-line elimination in terrains
15 Citations1992Franco P. Preparata, Jeffrey Scott Vitter
International Journal of Geographical Information SystemsDiscrete visibility problems and graph algorithms
15 Citations1997Enrico Puppo, Paola Marzano
This paper shows that graph algorithms can be useful to find efficient solutions for discrete visibility problems in several cases, and gives some practical rules to apply such an approach.
Concurrency Practice and ExperienceRegion‐to‐region visibility analysis using data parallel machines
12 Citations1993Yuan‐Hsiang Teng, Daniel DeMenthon +1 more
The algorithm focuses on the reduction of global communication by exploring the coherence properties in the processor structure and designed rules of decomposition to efficiently handle the cases where the required number of processors is greater than available.
Lecture notes in computer scienceRemembering conflicts in history yields dynamic algorithms
11 Citations1993Katrin Dobrindt, Mariette Yvinec
A general scheme to obtain dynamic algorithms which is based on the abstract setting introduced by Clarkson and Shor is proposed, which uses a novel data structure that combines the conflict graph and the history structure used by incremental algorithms.
Conference On Spatial Information TheoryUpdating Visibility Information on Multiresolution Terrain Models.
5 Citations1995Paola Magillo, Leila De Floriani +1 more