RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析
文献类型：期刊论文
| 作者 | 范俊甫1; 孔维华1; 马廷3 ; 周成虎3; 季民2; 周玉科3
|
| 刊名 | 测绘学报
 |
| 出版日期 | 2015 |
| 卷号 | 44期号:3页码:338 |
| 关键词 | 栅格化 多边形裁剪 点面包含 环绕追踪 面积误差 |
| ISSN号 | 1001-1595 |
| 英文摘要 | 传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N)~O(N~2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法-RaPC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效。 |
| 语种 | 英语 |
| 源URL | [http://ir.igsnrr.ac.cn/handle/311030/154819]  |
| 专题 | 中国科学院地理科学与资源研究所 |
| 作者单位 | 1.山东理工大学 2.山东科技大学 3.中国科学院地理科学与资源研究所 |
| 推荐引用方式 GB/T 7714 | 范俊甫,孔维华,马廷,等. RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析[J]. 测绘学报,2015,44(3):338. |
| APA | 范俊甫,孔维华,马廷,周成虎,季民,&周玉科.(2015).RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析.测绘学报,44(3),338. |
| MLA | 范俊甫,et al."RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析".测绘学报 44.3(2015):338. |
入库方式： OAI收割
来源：地理科学与资源研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。