A Procedure to Generate Thiessen Polygons

Geographical Analysis - Tập 11 Số 3 - Trang 289-303 - 1979
Kurt E. Brassel1, Douglas Reif1,2
1Kurt E. Brassel is assistant professor of geography, State University of New York at Buffalo.
2Some preliminary studies leading to this algorithm have been initiated by Dr. Thomas Peucker, Simon Fraser University, and have been supported by ONR Contract N00014–75–0886. Mr. Robert Fowler, Simon Fraser University, has pointed out and corrected some important shortcomings of a preliminary version of this algorithm. The implementation of the present procedure has been supported by the Erie and Niagara Counties Regional Planning Board. Mr. George Sicherman reviewed the manuscript and provided substantial help in formulating the proof section of this paper. Mr. Mike Wasilenko executed the illustrations. The authors gratefully acknowledge all these contributions.

Tóm tắt

An algorithm to generate Thiessen diagrams for a set of n points defined in the plane is presented. First, existing proximal polygon computation procedures are reviewed and terms are defined. The algorithm developed here uses a rectangular window within which the Thiessen diagram is defined. The computation of Thiessen polygons uses an iterative walking process whereby the processing starts at the lower left corner of the diagram and proceeds toward the right top corner. The use of a sorted point sequence and dynamical core allocation provide for efficient processing. The presentation is concluded by the discussion of an implementation of the algorithm in a FORTRAN program.

Từ khóa


Tài liệu tham khảo

Bentley J. L.“Divide and Conquer Algorithms for Closest Point Problems in Multidimensional Space”.Ph.D. thesis University of North Carolina at Chapel Hill 1976.

Bentley J. L. andM. I.Shamos.“Divide and Conquer in Multidimensional Space”. Proceedings of the Eighth Annual ACM Symposium on Theory of Computing Hershey Pa. 1976 pp.220–30.

Besag J., 1974, Spatial Interaction and the Statistical Analysis of Lattice Systems, Journal of the Royal Statistical Society (B), 36, 192

10.1111/j.1538-4632.1977.tb00590.x

Boots B. M., 1974, Delaunay Triangles: An Alternative Approach to Point Pattern Analysis, Proceedings of the Association of American Geographers, 6, 26

10.2307/490327

Brassel K. E.“Neighborhood Computations for Large Sets of Data Points”.Proceedings of the International Symposium on Computer‐Assisted Cartography(AUTO‐CARTO II). Washington D.C.: American Congress on Surveying and Mapping 1976 337–45.

Brassel K. E., 1978, A Topological Data Structure for Multi‐Element Map Processing, Harvard Papers on Geographic Data Structures, 4

10.1016/0098-3004(78)90082-1

Delaunay B.Sur la sphere vide.Bulletin of the Academy of Sciences of the USSR Classe Sci. Mat. Nat. (1934) 793–800.

Dobkin D. P., 1975, The Complexity of Searching Lines in the Plane

10.1137/0205015

Fisher H., 1970, Instructions for Establishing Proximal Zones

Fowler R. J., 1978, Approaches in Multi‐Dimensional Searching, Harvard Papers in Geographical Information Systems, 6

Fowler R. J., 1977, DELTRI: An Efficient Program for Producing Delaunay Triangulations

10.1214/aoms/1177704464

10.1093/comjnl/21.2.168

10.1287/opre.20.3.613

Knuth D. E., 1973, The Art of Computer Programming, Vol. 3: Sorting and Searching.

Laboratory for Computer Graphics and Spatial Analysis., 1975, SYMAP User's Reference Manual.

Lawson C. L., 1972, Generation of a Triangular Grid with Application to Contour Plotting

Lloyd E. L.“On Triangulations of a Set of Points in the Plane”.Master's thesis MIT 1977.

10.1093/comjnl/19.2.178

Mead R., 1971, Models for Interplant Competition in Irregularly Spaced Populations, Statistical Ecology, 2, 13

Nagy G., 1978, Geographic Data Processing

10.1559/152304075784447289

Peucker T. K. R. J.Fowler J. J.Little andD. M.Mark.“The Triangulated Irregular Network”.Proceedings of the Digital Terrain Models(DTM)Symposium American Society of Photogrammetry St. Louis 1978 516–40.

10.1111/j.1538-4632.1973.tb01003.x

Rogers C. A., 1964, Packing and Covering.

10.1109/TC.1978.1675001

Shamos M. I.“Computational Geometry”.Ph.D. thesis Yale University 1977.

Shamos M. I.“Geometric Complexity”.Proceedings of the Seventh ACM Symposium on the Theory of Computing(1975) 224–33.

Shamos M. I., 1978, Optimal Algorithms for Structuring Geographic Data, Harvard Papers on Geographical Information Systems, 6

Shamos M. I. andD.Hoey.“Closest Point Problems”.Proceedings of the Sixteenth Annual Symposium on the Foundations of Computer Science IEEE (1975) 151–62.

Sibson R.“Locally Equiangular Triangulations”. Unpublished manuscript.

10.1175/1520-0493(1911)39<1082b:PAFLA>2.0.CO;2

10.1515/crll.1908.134.198

10.1175/1520-0493(1929)57<462:ARE>2.0.CO;2

Wirth N., 1975, Algorithms + Data Structures = Programs.

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

Geographical Analysis

Tập 11 Số 3

289-303

Thông tin tác giả