| RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析 |
| |
| 引用本文： | 范俊甫,孔维华,马廷,周成虎,季民,周玉科.RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析[J].测绘学报,2015,44(3):338-345. |
| |
| 作者姓名： | 范俊甫 孔维华 马廷 周成虎 季民 周玉科 |
| |
| 作者单位： | 1. 山东理工大学建筑工程学院, 山东 淄博 255049;2. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室, 北京 100101;3. 山东科技大学测绘科学与工程学院, 山东 青岛 266590 |
| |
| 基金项目： | 国家自然科学基金(41471330);国家科技支撑计划(2012BAH27B04);中国科学院重点部署项目(KZZD-EW-07);山东省自然科学基金(ZR2012DL06);山东理工大学博士科研基金(4041-414039)~~ |
| |
| 摘 要： | 传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N)~O(N2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效。
|
| 关 键 词： | 栅格化 多边形裁剪 点面包含 环绕追踪 面积误差 |
| 收稿时间： | 2014-01-10 |
| 修稿时间： | 2014-10-11 |
RaPC:A Rasterization-based Polygon Clipping Algorithm and Its Error Analysi s |
| |
| FAN Junfu
,
KONG Weihua
,
MA Ting
,
ZHOU Chenghu
,
JI Min
,
ZHOU Yuke.RaPC:A Rasterization-based Polygon Clipping Algorithm and Its Error Analysi s[J].Acta Geodaetica et Cartographica Sinica,2015,44(3):338-345. |
| |
| Authors: | FAN Junfu KONG Weihua MA Ting ZHOU Chenghu JI Min ZHOU Yuke |
| |
| Institution: | 1. School of Civil and Architectural Engineering, Shandong University of Technology, Zibo 255049, China;2. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences, Beijing 100101, China;3. College of Geomatics, Shandong University of Science and Technology, Qingdao 266590, China |
| |
| Abstract: | Computational efficiencies of traditional vector computing‐based polygon clipping algorithms will decrease rapidly when handling polygons contain large amount of vertices .The computing flows of traditional polygon clipping algorithms are tightly coupled with special data structures ,which difficult to be optimized in the underlying of them .Under the premise of meeting a certain degree of area errors ,the polygonclippingproblemcanbesolvedbyintroducingtheideaofrasterizationprocessing.Inthisresearch, we proposed a new rasterization processing‐based polygon clipping algorithm:the RaPC algorithm ,on the basis of analyzing the characteristics of existing algorithms .The area errors of results of the new algorithm are also analyzed and discussed .Experimental results show that the efficiencies of the RaPC algorithm can be enhanced significantly when using l arge grid cells ,and it shows a linear trend growth with the increase of amount of polygon vertices .Compared with the Vatti algorithm ,the RaPC algorithm represents more efficiencies on dealing clipping issues between polygons with large amount of vertices ,the former shows lower time costs when handling polygons with less vertices .The area error of computing results of the RaPC algorithmiscloselyrelatedwiththegridsize,anderrorscanbereducedusingsmallergridsizes.Therefore the RaPC algorithm showed higher efficiencies on processing polygons with large amount of vertices than the Vatti algorithm and presented practical values to some degree . |
| |
| Keywords: | rasterization polygon clipping point in polygon winding and tracing area error |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《测绘学报》浏览原始摘要信息 |
| 点击此处可从《测绘学报》下载免费的PDF全文 |
|
