基于图模型的多边形自动并行构建算法

目前GIS基础算法并行化成为高性能GIS进一步深入的前提,作为GIS空间分析基础算法的重点,有必要对多边形构建提出一种自动并行算法。为此,提出基于图模型的多边形自动并行构建算法。该算法根据图模型中有向闭合环的特点对一组线段的集合进行多边形构建,能有效提高多边形构建的自动化程度。将搜索、排序等耗时较多的操作进行并行化处理,能有效减少全局搜索次数及整体排序和逻辑操作时间。实验表明,在对大规模线性数据生成区域时,该算法能有效地实现效率提升,达到良好的效果。

Automatic parallel polygonization algorithm based on graph model

Polygonization is always the emphasis in the basic algorithms of GIS spatial analysis. And the parallel processing of basic algorithms is the prerequisite for further progress of high performance GIS. For the computing requirements of parallel GIS, this paper put forward a parallel polygonization algorithm based on the graph model. The algorithm could effectively increase the degree of automation for polygonization, through constructed polygons according to the characteristics of graph model with directed rings. And it significantly reduced the number of global scan operations and the time of permutation and elementwise operations. The experimental result shows this algorithm has good ceffect for efficiency improvement when determining polygons formed by a large-scale line set.