RaPC：一种基于栅格化思想的多边形裁剪算法及其误差分析

• 作者: 周成虎 周玉科 孔维华 季民 范俊甫 马廷
• 来源期刊: 测绘学报
• 学科: 地球科学
• 关键词: 栅格化 多边形裁剪 点面包含 环绕追踪 面积误差
• 年，卷（期）: 2015,（3）
• 所属期刊栏目: [地图学与地理信息]
• 页码范围: 338-345
• 页数: 8页
• 分类号: P208
• 字数: 4639字
• 语种: 中文
• DOI: 10.11947/j.AGCS.2015.20140017

摘要

传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O（Nlog N ）～ O（N 2）之间，且计算过程与特定的复杂数据结构耦合紧密，难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下，采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上，提出了一种基于栅格化处理思想的多边形裁剪算法———R a PC算法，并对其误差进行了分析和讨论。试验结果显示，RaPC算法的计算效率随网格单元增大呈幂函数规律降低；当网格大小恒定时，RaPC算法效率随多边形顶点数量呈线性增长，计算时间复杂度为O（N）；在处理小数据集时Vatti算法表现出了较高效率，但是在处理包含大量顶点的多边形叠加时，RaPC算法更为高效；RaPC算法的面积误差与网格大小直接相关，提高网格空间分辨率可以有效地降低面积误差。R a PC算法在处理包含大量顶点的多边形叠加分析时比V atti算法更为高效。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周成虎	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	263	12312	58.0	102.0
2	孔维华	山东理工大学建筑工程学院	33	139	7.0	10.0
3	范俊甫	山东理工大学建筑工程学院	12	125	6.0	11.0
5	马廷	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	25	476	11.0	21.0
6	季民	山东科技大学测绘科学与工程学院	96	525	11.0	18.0