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 13:58 |
|