Conceptually, each input map is a planar graph composed of vertices and edges partitioning the two-dimensional plane into polygons. The graph may be disconnected with the components either nested or disjoint. Each polygon has a name, or identification number, which may be non-unique when one logical region is composed of several polygons, such as two parts of Michigan state. OVERPROP neither knows nor cares, but returns the total area of all of them. By convention, the outside of the map is polygon #0.
In our map data structure, the polygons are not represented
explicitly, but could be recreated if desired since each edge
knows its neighboring polygons. We assume that each input map is
a set of vertex coordinates: 
, and a set of tagged edges:
, where 
is the vertex that is the
edge's first endpoint, and 
is the second. 
are
the names of the polygons to the left and right.
In fact, this program reads chains of points in the Harvard Odyssey CDB format, and immediately splits them into the individual edges. See section 7.1 below for more details.
Each edge of each polygon has two endpoints (vertices), each of which
defines a ``half-edge'', e. Since a data structure edge borders
two polygons, it decomposes into four half-edges. Although the
half-edges are not explicit data structure elements, they can be derived
easily, and are important in the following algorithm. A half-edge
contains the information 
. 
is the
number of the vertex that is the endpoint. 
is a unit
tangent vector from the endpoint along the edge, and 
is
a unit normal vector perpendicular to the tangent, and pointing into the
polygon. For example, see edge 
in figure 1. The
edge is 
long, so the unit tangent from 
to 
is 
. The unit normal to that, pointing into
polygon 
, is 
. Therefore, the half-edge for the
side of the end of the edge is 
. The other three half edges are the 
side
of the end: 
, and the and
sides, respectively of the end: 
and 
.
A polygon number of the output map is an ordered pair 
of
the two input polygons whose intersection forms this particular output
polygon. Internally, to save space, the hash-addresses of the input
polygons are used instead of their id numbers.
Figure 1: Splitting an Edge into Half-Edges