一种有效的复杂多边形裁剪算法

An Efficient Algorithm for Complex Polygon Clipping

提出了一种基于扫描线思想和梯形分割技术的多边形裁剪算法,其主要步骤包括:计算主多边形(集)与窗口多边形(集)的交点,提取所有交点和多边形边界结点的纵坐标(y)并进行排序;以排序后的y作水平扫描线,分别对主多边形和窗口多边形进行梯形分割,获得两组梯形集合;对这两组梯形集合逐行执行梯形单元"交"运算,最后对结果交集进行边界追踪建立裁剪多边形。实验结果表明,该算法具有较好的计算效率,是一种比较实用的多边形裁剪算法。

We popose pezlum segmentation an efficient algorithm for complex polygon clipping by adopting the tra technique and scan line idea. Firstly, we find and compute the intersec tion points between main polygons and window polygons, then we record and sort the Y val- ues of these points and the points in all polygons. Secondly, we cut all the polygons into some trapezium units by drawing the scan lines on the basis of these Y values and intersecting the edges of all polygons with the scan lines. Thirdly, we complete the trapezium-split oper- ation line by line and pick up the intersection parts between the trapezia from main polygons and those from window polygons. Finally, we acquire the clipping polygons by tracing the boundary of the intersection parts. This algorithm ovecomes the complex computations such as the line reorganization and calculation of entry and exit points on the polygons.