王慧青　　崇素文

(1东南大学仪器科学与工程学院, 南京210096)(2展讯通信(上海)有限公司, 上海 201203)



一种处理交点退化现象的高效多边形裁剪算法

王慧青1崇素文2

(1东南大学仪器科学与工程学院, 南京210096)(2展讯通信(上海)有限公司, 上海 201203)

针对复杂多边形裁剪中出现的多边形彼此间重点和重边现象，提出了一种能够处理交点退化现象的高效多边形裁剪算法.该算法利用单向链表实现多边形的存储，同时基于单调链的平面扫描法求解多边形间的交点，减少了多边形顶点的遍历次数和求交次数；对于重点和重边现象，通过交点关联的线段间的方向关系判别交点的进出性；最后更新多边形顶点序列，获取裁剪结果.实验结果表明，该算法能够完成对含内环多边形的裁剪，在交点退化情况下也能获得准确的裁剪结果.且该算法裁剪效率较Greiner-Hormann算法大幅提高，具有很高的执行效率和实用性.

多边形裁剪;交点退化;单向链表;方向关系

多边形裁剪算法被广泛地应用于计算机图形学、地理信息系统(GIS)[1]及相关领域,其目的是提取裁剪多边形与主多边形(被裁剪多边形)的相交区域.常用的裁剪算法有Weiler-Atherton算法[2]、Vatti算法[3]及Greiner-Hormann算法[4],后两者在复杂性和运行效率方面优于前者,但都能实现对一般多边形的裁剪.为了进一步提高裁剪效率及处理复杂多边形裁剪问题,刘勇奎等[5]以Greiner-Hormann算法为基础,优化了交点数据结构和计算方法,提出了两多边形的边重合或者两多边形在……