Calculating the area of overlaid polygons without constructing the overlay

Abstract

An algorithm and implementation for calculating the areas of overlaid polygons without calculating the overlay itself, is presented. Overprop is useful when the sole purpose of overlaying two maps is to find some mass property of the resulting polygons, or for an areal interpolation of data from one map to the other. Finding the areas of all the output polygons is both simpler and more robust than finding the polygons themselves. Overprop works from a reduced representation of each map as a set of "half-edges"; with no global topology. It uses the uniform grid to find edge intersections. The method is not statistical, but is exact within the arithmetic precision of the machine. It is well-suited to a parallel machine, and could be extended to overlaying more than two maps simultaneously, and to determining other properties of the output polygons, such as perimeter or center of mass. Overprop has been implemented as a C program, and is very fast. The execution time on a Sun Sparcstation 10/30 to combine US counties, with 55,068 vertices and 2985 polygons with hydrography polygons, with 76,215 vertices and 2075 polygons, was 19 CPU seconds, excluding I/O time. This included the subtask of locating all the points of each map in a specific polygon of the other, which is a useful application in its own right. © 1994 Taylor & Francis Group, LLC.