Derivation of All Figures Formed by the Intersection of Generalized Polygons

In the course of a project related to computer-aided integrated circuit mask design, it became necessary to describe the configuration which is formed when two polygon-like plane figures are superimposed on one another. Two closed figures in a plane divide the plane into four regions: inside both figures, inside, the tirst. but not the second, inside the second but not the first, and inside neither. Each region may consist of one or more figures. Assuming t h a t the original figures consist of an arbitrary number of sides, each of which may be a line or circular arc segment, it was desired to describe every figure resulting from their intersection and to assign each to one of the four regions. The simple approach of establishing a grid of points and determining which sets of points are included in each region was not considered applicable, because the number of grid points required for sufficient resolution would have led to excessive computation. Instead, the following approach was used. Pairs of sides, one from each input figure, 1595