Derivation of All Figures Formed by the Intersection of Generalized Polygons
Michael Yamin · Bell System Technical Journal · 1972
A computer program is described which generates every intersection figure resulting from the superposition of two closed polygon-like plane figures, each consisting of an arbitrary number of line segments or circular arc segments. Each intersection figure is assigned to one of four regions of the plane, representing the union, the intersection, and the two “exclusive-or's” formed by the pair of input figures. The two input figures may intersect or be tangent at any number of points and may have sections of coincident boundaries. No grid approximation is used. The program operates in two stages: the first stage analytically finds and classifies every point of intersection or tangency of the figures; the second stage regards these points as the nodes of a graph and applies an algorithm which causes each intersection figure to be traced just once.