王结臣, 沈定涛, 陈焱明, 李利番. 一种有效的复杂多边形裁剪算法[J]. 武汉大学学报 ( 信息科学版), 2010, 35(3): 369-372.
引用本文: 王结臣, 沈定涛, 陈焱明, 李利番. 一种有效的复杂多边形裁剪算法[J]. 武汉大学学报 ( 信息科学版), 2010, 35(3): 369-372.
WANG Jiechen, SHEN Dingtao, CHEN Yanming, LI Lifan. An Efficient Algorithm for Complex Polygon Clipping[J]. Geomatics and Information Science of Wuhan University, 2010, 35(3): 369-372.
Citation: WANG Jiechen, SHEN Dingtao, CHEN Yanming, LI Lifan. An Efficient Algorithm for Complex Polygon Clipping[J]. Geomatics and Information Science of Wuhan University, 2010, 35(3): 369-372.

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

An Efficient Algorithm for Complex Polygon Clipping

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

     

    Abstract: We popose an efficient algorithm for complex polygon clipping by adopting the trapezium segmentation technique and scan-line idea.Firstly,we find and compute the intersection points between main polygons and window polygons,then we record and sort the Y values 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 operation 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.

     

/

返回文章
返回