简单多边形裁剪算法

作     者：宋树华 濮国梁 罗旭 陈东 陈润强 SONG Shu-hua;PU Guo-liang;LUO Xu;CHEN Dong;CHEN Run-qiang

作者机构：北京大学遥感与地理信息系统研究所北京100871 中国资源卫星应用中心北京100094 中煤科技集团公司北京100013 北京应用气象研究所北京100029 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2014年第35卷第1期

页      码：192-197页

摘      要：为了尽量降低任意多边形裁剪复杂度,提出了一种基于多边形顶点遍历的简单多边形裁剪算法。该算法将多边形交点插入到裁剪多边形和被裁减多边形顶点矢量数组中,通过记录交点及其前驱、后继信息,可快速生成结果多边形。其中,时间复杂度为O((m+k)×k),m是两多边形中顶点数较大者,k是两多边形的交点数。该算法简化了交点的数据结构,节省了存储空间,降低了算法的时间复杂度,具有简单、易于编程实现、运行效率高的特点。

主 题 词：多边形裁剪 交点 前驱 后继 矢量数组 

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1000-7024.2014.01.036

馆 藏 号：203935223...