%0 Journal Article
%T RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析
%A 范俊甫
%A 孔维华
%A 马廷
%A 周成虎
%A 季民
%A 周玉科
%J 测绘学报
%P 338-345
%D 2015
%R 10.11947/j.AGCS.2015.20140017
%X 传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(NlogN)~O(N2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化.在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪.本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论.试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为ON;在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差.RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效.
%K 栅格化
%K 多边形裁剪
%K 点面包含
%K 环绕追踪
%K 面积误差
%U http://xb.sinomaps.com:8081/Jwk_chxb/CN/abstract/abstract6508.shtml