分治法在GIS多边形快速合并算法中的应用及效率提升评价模型
文献类型：期刊论文
| 作者 | 范俊甫; 马廷; 周成虎; 周玉科; 许涛 |
| 刊名 | 地球信息科学学报
 |
| 出版日期 | 2014 |
| 卷号 | 16期号:2页码:158 |
| 关键词 | polygon union snowball union tree-like union divide-and-conquer method efficiency evaluation 多边形合并 “滚雪球”合并 “树状”合并 分治法 效率评价 |
| ISSN号 | 1560-8999 |
| 英文摘要 | 分治法采用分解-解决-合并的问题处理模式,应用于多边形合并算法能规避结点累积效应,与经典的“滚雪球”处理模式相比能有效提升多边形合并算法的计算效率。本文以多边形合并算法为研究对象,首先通过分析基于Vatti算法实现的多边形合并算子的效率相对于多边形顶点数的变化特征,指出合并过程中的结点累积效应是“滚雪球”多边形合并模式的潜在性能瓶颈和隐患。考虑分治法的“分而治之”思想在解决多边形合并问题上的适用性以及在归并排序算法中表现出的高效率,提出分治法的多边形“树状”合并处理模式,实现了面向要素集合或者要素层的多边形快速合并算法,最后给出了面向多边形合并的算法效率提升评价模型。实验结果显示,当仅有400个多边形时,“滚雪球”模式的时间开销约是“树状”合并模式的26倍,当需要合并11200个多边形时,前者的时间开销约是后者的926倍。因此,基于分治法的多边形树状合并策略是对多边形合并算法以及应用到多边形合并算法的高级空间分析算法进行优化的可行途径。 |
| 语种 | 英语 |
| 源URL | [http://ir.igsnrr.ac.cn/handle/311030/193297]  |
| 专题 | 中国科学院地理科学与资源研究所 |
| 作者单位 | 中国科学院地理科学与资源研究所 |
| 推荐引用方式 GB/T 7714 | 范俊甫,马廷,周成虎,等. 分治法在GIS多边形快速合并算法中的应用及效率提升评价模型[J]. 地球信息科学学报,2014,16(2):158. |
| APA | 范俊甫,马廷,周成虎,周玉科,&许涛.(2014).分治法在GIS多边形快速合并算法中的应用及效率提升评价模型.地球信息科学学报,16(2),158. |
| MLA | 范俊甫,et al."分治法在GIS多边形快速合并算法中的应用及效率提升评价模型".地球信息科学学报 16.2(2014):158. |
入库方式： OAI收割
来源：地理科学与资源研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。