分治法在GIS多边形快速合并算法中的应用及效率提升评价模型

摘要：

分治法采用分解-解决-合并的问题处理模式，应用于多边形合并算法能规避结点累积效应，与经典的“滚雪球”处理模式相比能有效提升多边形合并算法的计算效率。本文以多边形合并算法为研究对象，首先通过分析基于Vatti算法实现的多边形合并算子的效率相对于多边形顶点数的变化特征，指出合并过程中的结点累积效应是“滚雪球”多边形合并模式的潜在性能瓶颈和隐患。考虑分治法的“分而治之”思想在解决多边形合并问题上的适用性以及在归并排序算法中表现出的高效率，提出分治法的多边形“树状”合并处理模式，实现了面向要素集合或者要素层的多边形快速合并算法，最后给出了面向多边形合并的算法效率提升评价模型。实验结果显示，当仅有400个多边形时，“滚雪球”模式的时间开销约是“树状”合并模式的26倍，当需要合并11200个多边形时，前者的时间开销约是后者的926倍。因此，基于分治法的多边形树状合并策略是对多边形合并算法以及应用到多边形合并算法的高级空间分析算法进行优化的可行途径。

关键词：多边形合并、“滚雪球”合并、“树状”合并、分治法、效率评价

分类号：TP3;O24

资助基金：国家科技支撑计划项目2011BAH06B03、2011BAH24B10；中国科学院重点部署项目KZZD-EW-07。

在线出版日期：2014-03-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：158-164