Coverage problems and visibility regions on topographic surfaces

Springer Science and Business Media LLC - Tập 18 - Trang 175-186 - 1989
Michael F. Goodchild1, Jay Lee1
1Department of Geography, University of Western Ontario, London, Canada

Tóm tắt

The viewshed of a point on an irregular topographic surface is defined as the area visible from the point. The area visible from a set of points is the union of their viewsheds. We consider the problems of locating the minimum number of viewpoints to see the entire surface, and of locating a fixed number of viewpoints to maximize the area visible, and possible extensions. We discuss alternative methods of representing the surface in digital form, and adopt a TIN or triangulated irregular network as the most suitable data structure. The space is tesselated into a network of irregular triangles whose vertices have known elevations and whose edges join vertices which are Thiessen neighbours, and the surface is represented in each one by a plane. Visibility is approximated as a property of each triangle: a triangle is defined as visible from a point if all of its edges are fully visible. We present algorithms for determination of visibility, and thus reduce the problems to variants of the location set covering and maximal set covering problems. We examine the performance of a variety of heuristics.

Từ khóa


Tài liệu tham khảo

K.E. Brassel and D. Reif, A procedure to generate Thiessen polygons, Geographical Analysis 11 (1979) 289.

P.A. Burrough,Principles of Geographic Information Systems for Land Resources Assessment (Oxford University Press, 1986).

R.L. Church and C.S. Revelle, The maximal covering location problem, Papers, Regional Science Association 32 (1974) 101.

L. de Floriani, B. Falcidieno and C. Pienovi, Delaunay-based representation of surfaces defined over arbitrarily shaped domains, Computer Graphics, Vision and Image Processing 32 (1985) 127.

L. de Floriani, B. Falcidieno, C. Pienovi, D. Allen and G. Nagy, A visibility-based model for terrain features,Proceedings, Second International Symposium on Spatial Data Handling, Seattle (1986) 235.

D.T. Lee and B.J. Schachter, Two algorithms for constructing a Delaunay triangulation, International Journal of Computer and Information Sciences 9 (1980) 219.

B.B. Mandelbrot,The Fractal Geometry of Nature (Freeman, San Francisco, 1982).

D.M. Mark, Recursive algorithm for determination of proximal (Thiessen) polygons in any metric space, Geographical Analysis 19 (1987) 264.

T.K. Peucker, R.J. Fowler, J.J. Little and D.M. Mark, The triangulated irregular network, Proceedings, Digital Terrain Models Symposium, ASP/ACSM (1978) 516.

C. ReVelle, Personal communication, 1987

A. Tarvydas, Terrain approximation by triangular facets, Paper prepared for AutoCarto 6, Ottawa, 1983.

C. Toregas and C. ReVelle, Optimum location under time and distance constraints, Papers and Proceedings, Regional Science Association 28 (1972) 133.

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 18

175-186

Thông tin tác giả