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.
Get full access to this article
View all access options for this article.
References
1.
AttallahM, 1983, “Dynamic computational geometry”, in Proceedings of the 24th IEEE Symposium on Foundations of Computer Science (IEEE Computer Society, Washington, DC) pp 92–99
2.
BlellochG E, 1990Vector Models for Data-parallel Computing (MIT Press, Cambridge, MA)
3.
BruzzoneEDe FlorianiLMagilloP, 1995, “Updating visibility information on multiresolution terrain models”, in Proceedings of the Conference on Spatial Information Theory (COSIT 95) Eds FrankA UKuhnW (Springer, Berlin) pp 279–296
4.
ColeRSharirM, 1989, “Visibility problems for polyhedral terrains”Journal of Symbolic Computation1711–30
5.
De FlorianiLMagilloP, 1995, “Horizon computation on a hierarchical terrain model”The Visual Computer: An International Journal of Computer Graphics11134–149
6.
De FlorianiLMagilloP, 1997, “Visibility computations on hierarchical triangulated terrain models”Geoinformatica1(3) 219–250
7.
De FlorianiLMagilloP, 2002, “Multiresolution mesh representation: Models and data structures”, in Tutorials on Multiresolution in Geometric Modelling Eds IskeAQuakEFloaterM S (Springer, Berlin) pp 363–418
8.
De FlorianiLFalcidienoBNagyGPienoviC, 1989, “Polyhedral terrain description using visibility criteria”, TR, Institute for Applied Mathematics, National Research Council, Genova
9.
De FlorianiLFalcidienoBNagyGPienoviC, 1991, “On sorting triangles in a Delaunay tesselation”Algoritmica6522–532
10.
De FlorianiLMontaniCScopignoR, 1994, “Parallelizing visibility computations on triangulated terrains”International Journal of Geographical Information Systems, 515–532
11.
DobrindtKYvinecM, 1993, “Remembering conflicts in history yields dynamic algorithms”, in Algorithms and Computation Eds NgK WRaghavanPBalasubramanianN VChinF Y L (Springer, Hong Kong) pp 21–30
12.
FellemanJ PGriffinC, 1990, “The role of error in GIS-based viewshed determination—a problem analysis”, TR EIPP-90-2, State University of New York, Institute for Environmental Policy and Planning, Albany, NY
13.
FisherP F, 1993, “Algorithms and implementation of uncertainty in viewshed analysis”International Journal of Geographic Information Systems7331–347
14.
FisherP F, 1995, “An exploration of probable viewsheds in landscape planning”Environment and Planning B: Planning and Design22527–546
15.
FisherP F, 1996a, “Extending the applicability of viewsheds in landscape planning”Photogrammetric Engineering and Remote Sensing621297–1302
16.
FisherP F, 1996b, “Reconsideration of the viewshed function in terrain modeling”Geographic Systems333–58
17.
FranklinW R, 2002, “Siting observers on a terrain”, in Proceedings of the International Symposium on Spatial Data Handling 2002 Eds RichardsonDvan OosteromP (Springer, Berlin)
18.
FranklinW RRayC, 1994, “Higher is not necessarily better: Visibility algorithms and experiments”, in Advance in GIS Research, Proceedings of the 6th International Symposium on Spatial Data Handling Eds WaughT CHealeyR G (Taylor and Francis, London) pp 751–770
19.
HershbergerJ, 1989, “Finding the upper envelope of” line segments in O(n log ri) timeInformation Processing Letters33169–174
20.
KatzM JOvermarsM HSharirM, 1991, “Efficient hidden surface removal for objects with small union size”, in Proceedings of the 7th ACM Symposium on Computational Geometry (ACM Press, New York) pp 31–40
21.
KirkpatrickD G, 1983, “Optimal search in planar subdivision”SIAM Journal of Computing12(1) 28–33
22.
LeeJ, 1991, “Analyses of visibility sites on topographic surfaces”International Journal of Geographical Information Systems5413–429
23.
LeeJPreparataF P, 1977, “Location of a point in a planar subdivision and its applications”SIAM Journal of Computing6594–606
24.
MillsKFoxGHeimbachR, 1992, “Implementing an intervisibility analysis model on a parallel computing system”Computers and Geosciences181047–1054
25.
NagyG, 1994, “Terrain visibility”Computer and Graphics18763–773
26.
O'SullivanDTurnerA, 2001, “Visibility graphs and landscape visibility analysis”International Journal of Geographic Information Science15221–237
27.
PreparataF PShamosM I, 1985Computational Geometry: An Introduction (Springer, Berlin)
28.
PreparataF PVitterJ S, 1992, “A simplified technique for hidden-line elimination in terrains”, in STACS '92 Eds FinkelAJantzenM (Springer, Berlin) pp 135–144
29.
PuppoEMarzanoP, 1997, “Discrete visibility problems and graph algorithms”International Journal of Geographical Information Systems11139–161
30.
RailingsP JWareJ AKidnerD B, 1998, “Parallel distributed viewshed analysis”, in Proceedings of ACMGIS '98 (ACM Press, New York) pp 151–156
31.
ReifJSenS, 1988, “An efficient output-sensitive hidden surface removal algorithm and its parallelization”, in Proceedings of the 4th ACM Symposium on Computational Geometry (ACM Press, New York) pp 193–200
32.
SarnakNTarjanR E, 1986, “Planar point location using persistent search trees”Communications of the ACM29(7) 669–679
33.
ShapiraA, 1990, “Visibility and terrain labelling”, masters thesis, Department of Electrical, Computer, and System Engineering, Rensselaer Polytechnic Institute, Troy, NY
34.
SorensenPLanterD, 1993, “Two algorithms for determining partial visibility and reducing data structure induced error in viewshed analysis”Photogrammetric Engineering and Remote Sensing591129–1132
35.
StewartA J, 1998, “Fast horizon computation at all points of a terrain with visibility and shadow applications”IEEE Transactions on Visualization and Computer Graphics4(1) 82–93
36.
TengY ADe MenthonDDavisL S, 1993, “Region-to-region visibility analysis using data parallel machines”Concurrency: Practice and Experience5379–406
37.
TengY AMountDPuppoEDavisL S, 1995, “Parallelizing an algorithm for visibility on polyhedral terrain”International Journal of Computational Geometry and Applications7(1–2) 75–84
38.
Van KreveldM, 1996, “Variations on sweep algorithms: Efficient computation of extended viewsheds and class intervals”, in Proceedings of the Symposium on Spatial Data Handling '96 (Eds KraakM JMolenaarM, Faculty of Geodetic Engineering, Delft University of Technology, Delft) pp 13A.15–13A.27
