(in WR FranklinResearch)

An algorithm 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.

One useful subtask is to locate all the points of each map in a specific polygon of the other. Its expected execution time is constant per query point regardless of the other map's complexity.

The largest example intersected counties of the coterminous US against hydrography polygons. They have these stats:

 Map #0: 55068 vertices, 46116 edges, 2985 polygons
Map #1: 76215 vertices, 69835 edges, 2075 polygons


The total CPU time, in seconds, on an IBM T30 Thinkpad with a 1600MHz Pentium is about:

  Execution times:
Scale vertices:                0.02
Extract edges:                 0.08
Calculate areas:               0.08
Make grid:                     0.00
Intersect edges:               0.13
Locate map 0 points in map 1:  0.40
Locate map 1 points in map 0:  0.48
Accumulate areas:              0.28
Print areas:                   0.20

TOTAL TIME=                       2.65


Papers

1. Wm Randolph Franklin and Venkatesh Sivaswami. OVERPROP — Calculating Areas of Map Overlay Polygons without Calculating the Overlay. In Second National Conference on Geographic Information Systems, pages 1646-1654, Ottawa, 5-8 March 1990. (paper).
2. Wm Randolph Franklin, Venkateshkumar Sivaswami, David Sun, Mohan Kankanhalli and Chandrasekhar Narayanaswami. Calculating the Area of Overlaid Polygons Without Constructing the Overlay. Cartography and Geographic Information Systems, Apr 1994. (paper). ]
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.
paper
3. Wm Randolph Franklin. Map Overlay Area Animation and Parallel Simulation. In David H. Douglas, editor, Proceedings, SORSA'92 Symposium and Workshop, pages 200-203, July 28-August 2 1992. (paper).
4. Wm Randolph Franklin. Calculating Map Overlay Polygon' Areas Without Explicitly Calculating the Polygons — Implementation. In 4th International Symposium on Spatial Data Handling, pages 151-160, Zürich, 23-27 July 1990. (paper).
5. Wm Randolph Franklin. A Simplified Map Overlay Algorithm. In Harvard Computer Graphics Conference, Cambridge, Mass, USA, 31 July - 4 August 1983. (paper).