适用于凹多边形的Cyrus-Beck改进算法

An Improved Algorithm of Cyrus-Beck Segment Clipping to Process Concave Polygon

本文对目前常用的二维线段裁剪算法进行分析,提出了一种基于Cyrus-Beck算法的改进算法,使其能够扩展到对凹多边形的处理,通过对线段与裁剪窗口位置关系的严格判断将求交次数减到最少,并且通过对交点性质的判断来识别出线段的可见部分。理论分析和实验结果均表明该算法优于目前处理任意多边形裁剪框的算法。

Based on the analysis of currently popular algorithms for segment clipping, in this paper, an improvement in the algorithm of Cyrus-Beck segment is proposed, which extends the algorithm to the range of concave polygon. The calculation of the intersection points is decreased to the minimum by the means of verifying the position of the line to be clipped against the polygon. And marking those intersection points with ＂in＂ or ＂out＂ to decide which subqine between the two intersection points is visible. Both theoretic analysis and example testing show that the new algorithm is better than well known algorithms.