关键词: 凹多边形, 多边形裁剪, 跟踪策略, 网格划分, 单线性链表

Abstract: An effective algorithm for polygon clipping which supports simple polygons
including concave polygons and polygons with holes inside is presented in this paper. This
algorithm can be used to calculate set-theoretic differences and union of two polygons. Most
analogous algorithms are classifying point of intersection by entry points and exit points, then
generating output polygons by tracing vertex. Different from these algorithms, this paper classifies
point of intersection by normal point of intersection and vertex of intersection, and designs
different tracing strategies for them. By using these strategies alternately and recursively, a steady
tracing process to cope with degenerate input is putted forward. To improve efficiency of edge
intersection, which is the bottleneck of polygon clipping, it partitions the polygon that has more
numbers of edges to grids and brings forward an algorithm for edge partition based on Bresenham
line-drawing algorithm. At the end of this paper, the algorithm is compared with the existing
algorithms and the result shows that it has higher speed than others.

Key words: concave polygons, polygon clipping, tracing strategy, grid partition, singly
linked list