The program may be viewed as first observing which edges of the first polygon intersect which edges of the second polygon, and the sense of the intersection.
Just two more observations are required: the winding number of vertex 0 of each polygon with respect to the other.
From these observations an expression in the vertex coordinates is selected and evaluated.
All conditional control of program flow, based on floating point input values are based solely on these observations.
Degenerate cases vastly outnumber the general cases!
Any degenerate case is very near a non degenerate case.
The area of the intersection is a continuous function of the vertex coordinates.
To handle degenerate cases we make all of these intersection observations on fudged coordinates.
This fudging is to bits beyond the significance of the 32 bit floating point inputs.
Without fudging, intersection observations will be incompatible and describe discontiguous curves leading to expressions that reflect no closed curve.
These wrong expression deliver grossly inaccurate results.
Each observation is made by calculating the sign of the area of a certain triangle, two of whose vertices are the ends of a side of a polygon
and whose other vertex is a vertex of the other polygon.
These areas are computed with no rounding, to a precision of 64 bits starting from the fudged coordinates.
The fudging ensures that such triangles are never degenerate, with zero area.
All such observations can be described as determining whether one polygon vertex is on the inside side of an edge of the other polygon.
These observations describe non degenerate polygon pairs that are within floating point precision of the delivered polygon pairs.
The Fudging Trick
How do we adjust the coordinates to insure that our test triangles are never degenerate?
A famous formula for the twice the area of a triangle is the determinant:
If we think modulo 8 then the low 3 bits of this determinant derive from the low 3 bits of the coordinates.
We fudge the low 3 bits of the coordinates to insure that the low 3 bits of the determinant are non-zero.
Recall that there is no rounding between fudging and area sign testing.
For the first polygon the coordinate are <0,0> for even vertices and <0,1> for odd vertices, all modulo 8 except when there are an odd number of vertices and vertex 0 is <1,0> mod 8.
All of the coordinates of the second polygon are 2 higher.
It can be seen that in the cartesian space below, no degenerate triangles may be formed from a side of one polygon and a vertex of the other.
Their determinant modulo 8 is thus never 0.
The full determinant is thus also never zero.
Alternatively you might be convinced by studying and running this exhaustive program.
