CAJ | 학술논문

分治法采用分解-解决-合并的问题处理模式，应用于多边形合并算法能规避结点累积效应，与经典的“滚雪球”处理模式相比能有效提升多边形合并算法的计算效率。本文以多边形合并算法为研究对象，首先通过分析基于Vatti算法实现的多边形合并算子的效率相对于多边形顶点数的变化特征，指出合并过程中的结点累积效应是“滚雪球”多边形合并模式的潜在性能瓶颈和隐患。考虑分治法的“分而治之”思想在解决多边形合并问题上的适用性以及在归并排序算法中表现出的高效率，提出分治法的多边形“树状”合并处理模式，实现了面向要素集合或者要素层的多边形快速合并算法，最后给出了面向多边形合并的算法效率提升评价模型。实验结果显示，当仅有400个多边形时，“滚雪球”模式的时间开销约是“树状”合并模式的26倍，当需要合并11200个多边形时，前者的时间开销约是后者的926倍。因此，基于分治法的多边形树状合并策略是对多边形合并算法以及应用到多边形合并算法的高级空间分析算法进行优化的可行途径。
분치법채용분해-해결-합병적문제처리모식，응용우다변형합병산법능규피결점루적효응，여경전적“곤설구”처리모식상비능유효제승다변형합병산법적계산효솔。본문이다변형합병산법위연구대상，수선통과분석기우Vatti산법실현적다변형합병산자적효솔상대우다변형정점수적변화특정，지출합병과정중적결점루적효응시“곤설구”다변형합병모식적잠재성능병경화은환。고필분치법적“분이치지”사상재해결다변형합병문제상적괄용성이급재귀병배서산법중표현출적고효솔，제출분치법적다변형“수상”합병처리모식，실현료면향요소집합혹자요소층적다변형쾌속합병산법，최후급출료면향다변형합병적산법효솔제승평개모형。실험결과현시，당부유400개다변형시，“곤설구”모식적시간개소약시“수상”합병모식적26배，당수요합병11200개다변형시，전자적시간개소약시후자적926배。인차，기우분치법적다변형수상합병책략시대다변형합병산법이급응용도다변형합병산법적고급공간분석산법진행우화적가행도경。
Vector data overlay analysis methods, with the most difficult and tricky core issue of overlapping be-tween polygons, are the basic analysis approaches for many spatial analysis algorithms in Geography Informa-tion System (GIS) software and also the basis for many advanced spatial analysis models and complex spatial analysis applications. The divide and conquer strategy, with the paradigm of divide-conquer-combine for prob-lem solving, can reduce the cumulative effects of nodes of the polygon union results at average level. And, com-pared with classic snowball union strategy, it can accelerate the polygon union algorithm effectively. In this re-search, we took the polygon union algorithm as an example to describe a fast polygon union strategy named tree-like union method. Firstly, we analyzed the variation of the efficiency of the core operator, which is polygon union operation implemented by Vatti’s algorithm, with different node number of polygons, and figured out that the potential performance bottlenecks and pitfalls of the snowball union strategy is the cumulative effect of the nodes existing in the union process. Then based on the idea of divide and conquer we proposed a new approach named tree-like union strategy and implemented a union algorithm for polygon clusters or layers to solve the problem in polygon union process. Finally, we introduced an efficiency evaluate model by which the available ac-celeration potentiality derived from the tree-like union strategy can be assessed conveniently for a group of poly-gons. Experimental results in this research shown that compared with snowball union strategy, the tree-like union strategy based on the idea of divide and conquer could lead to great reduction of time costs of polygon union al-gorithm. Furthermore, we found that the time cost of snowball union was about 26-folds than that of tree-like method when union 400 polygons, and the number reached about 926 when union 11 200 polygons. Therefore, it can be inferred that the accelerate effects brought by the tree-like union strategy could become more significant when dealing with larger polygon datasets. We supposed that the tree-like union strategy proposed in this re-search represents a certain degree of applicability in operations similar with polygon union algorithm, which could be a potential and practical optimization approach for vector data overlapping and other advanced spatial analysis algorithms which involved with polygon union operations.