If the polygons were simple with many edges that seldom crossed, then to first approximation we could identify the boundary of the intersection as composed of those edges whose first vertex has winding number one wrt the other polygon. Indeed the code: if(s) cntrib(P[j].ip, P[j+1].ip, s, "three"); fires on just those edges, but generalized to winding numbers other than 0 and 1. We shall see later how s comes to be the winding number. (Note the blue border of the edges. The winding number on the blue side is one more than the on the other side. For simple polygons, the blue side is inside.)

We must attend to just where two edges intersect, however. Consider an edge A, B of the first polygon and an edge C, D of the second polygon. (A and C are the respective first vertices. See figure 3.) If the four triangles (A, B, D), (A, C, D), (B, D, C), (D, A, B) all have positive areas then the two edges intersect. If they are all negative then exchanging the polygons makes these four triangles have positive area. Otherwise the edges do not intersect. We exclude degenerate cases that involve degenerate triangles of zero area.

Fig 3	Fig 4

For each such intersection, label the intersection X and add the subsegment X-D and deduct the subsegment X-B. We arrive then at figure 4. In general an edge can have many intersections. The order of these intersections is irrelevant to the logic of the program. Each intersection is an entry of one polygon boundary into the other polygon and concomitantly an exit of the other polygon’s boundary from the first. These comings and goings are counted in the field in of the vertex record and these counts efficiently track the winding numbers for each polygon vertex.

The nested routine cross runs for each such intersection and invokes cntrib for both subsegments. It also contributes to the in field of both involved edges.

cntrib is also invoked for each polygon edge if the winding number of its first vertex is not 0 with respect to the other polygon.

cntrib accumulates in s the algebraic sum of such area contributions and this sum is the area of the intersection of the polygons.