CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

PDF papers
authors Liang, You-Dong and Barsky, Brian A.
year 1983
title An Analysis and Algorithm for Polygon Clipping
source Communications of the ACM November, 1983. vol. 26: pp. 868-877 : ill. includes bibliography.
summary (This is one of the two standard algorithms for clipping. The other is the Sutherland-Hodgman reentrant algorithm). The process of polygon clipping is analyzed and the understanding gained thereby forms the foundation of a very direct algorithm. Each edge of the input polygon is considered to be a vector and is then extended to be a line of infinite extent. The boundary line segments of the clip window are extended in a similar fashion to become boundary lines. The intersection points of an extended edge with the boundary lines are identified as entry or exit points. It is observed that these entry and exit points can be used to characterize the visibility status of the edge. Not only might the edge have a visible segment, but it can also induce the inclusion in the output polygon of a vertex at a corner of the clip window called a turning vertex. To quantify the visibility conditions, the edge is written in parametric form. The possible contributions (including nil) that can be provided to the output polygon by a particular edge are established. This analysis is then embedded in an algorithm. An arbitrary example input polygon is given and the output of the algorithm is shown. The execution time for this example using this algorithm is measured to be half of what is required by the standard Sutherland-Hodgman reentrant polygon clipping algorithm
keywords polygons, clipping, algorithms, computer graphics
series CADline
references Content-type: text/plain
last changed 2003/06/02 11:58
pick and add to favorite papersHOMELOGIN (you are user _anon_109674 from group guest) CUMINCAD Papers Powered by SciX Open Publishing Services 1.002