Calculating the Area of Overlaid Polygons Without Constructing the Overlay

Wm Randolph Franklin
Venkateshkumar Sivaswami
David Sun
Mohan Kankanhalli
Chandrasekhar Narayanaswami
Rensselær Polytechnic Institute
Troy, NY, 12180 USA
Phone: +1 (518) 276-6077,
Fax: +1 (518) 276-6261
Internet: wrfATecse.rpi.edu

To appear in Cartography and Geographic Information Systems, March/April 1994.

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 55068 vertices and 2985 polygons with hydrography polygons, with 76215 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.

Wm Randolph Franklin
Wed Dec 14 14:03:28 EST 1994