Polygon Clipping and Polygon Reconstruction

Abstract. Polygon clipping is an important operation that computers execute all the time. An algorithm that clips a polygon is rather complex. Each edge of the polygon must be tested against each edge of the clipping window, usually a rectangle. As a result, new edges may be added, and existing edges may be discarded, retained, or divided. Multiple polygons may result from clipping a single polygon. After clipping, we may have a set of segments, which must be handled to generate the clipped polygon. This work proposes two new algorithms: clipping polygon against a rectangle window, and polygon reconstruction from a set of segments. The algorithms were implemented in Secondo, a platform for implementing and experimenting with various kinds of data models. 1