(in WR Franklin → Research)

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:
     Read map:                      0.87
     Scale vertices:                0.02
     Extract edges:                 0.08
     Calculate areas:               0.08
     Make grid:                     0.00
     Add map to grid:               0.10
     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

Code

Papers

bibtexsummary:[/wrf.bib,fs-ocamo-90-in-geom]
bibtexsummary:[/wrf.bib,fsskn-ofmop-93]]
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
bibtexsummary:[/wrf.bib,f-moaap-92]
bibtexsummary:[/wrf.bib,f-cmopa-90]
bibtexsummary:[/wrf.bib,fsmoa-83]

Papers

See also