A Procedure to Generate Thiessen Polygons

Abstract

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.