格网划分的双策略跟踪多边形裁剪算法

Polygon clipping algorithm based on dual-strategies tracing and grid partition

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单多边形,同时也支持多边形的"并"和"差"等布尔运算。首先,设计了算法所需的数据结构;其次,基于直线扫描转换Bresenham算法原理提出了边网格划分的有效算法,并应用一个简单的方法避免不同网格内边的重复求交;最后,将交点分类为普通交点和顶交点,并针对这两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处理特殊情况时的稳定性。与其它同类算法的比较表明,新算法具有更高的效率。

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.