Premium
A Procedure to Generate Thiessen Polygons
Author(s) -
Brassel Kurt E.,
Reif Douglas
Publication year - 1979
Publication title -
geographical analysis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.773
H-Index - 65
eISSN - 1538-4632
pISSN - 0016-7363
DOI - 10.1111/j.1538-4632.1979.tb00695.x
Subject(s) - polygon (computer graphics) , computation , computer science , voronoi diagram , algorithm , sequence (biology) , set (abstract data type) , process (computing) , mathematics , geometry , programming language , telecommunications , frame (networking) , biology , genetics
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.