利用缓冲区融合多边形算法

周义军

摘 要：多边形融合是自动化制图综合中的重要步骤。目前，这类算法的设计主要基于多边形几何特征、拓扑特征进行分析，建立一种合适空间数据模型，以此来支持多边形之间的临近关系的探测。通过这种思路，该文提出了一种基于缓冲区操作的多边形融合的算法，利用现有GIS系统普遍具有的缓冲区操作功能，进行合理的设计，从而达到多边形融合的效果。

关键词：多边形融合 正向缓冲区操作 负向缓冲区操作 双向缓冲区变换

中图分类号：P208 文献标识码：A 文章编号：1674-098X（2017）03（c）-0054-03

多边形融合算法在地图综合领域起着非常重要的作用，就目前来看，方法主要可为两类，基于栅格结构的算法和基于矢量数据的算法。

基于栅格结构的算法中，典型方法是应用数学形态学原理来实施多边形化简与合并，利于数学方法对图像进行膨胀、腐蚀、开运算、闭运算、集中、薄化和厚化等运算，算法速度与区域面积有关，区域图像越大计算量越大，综合质量依赖于硬件设备，另受模板结构和样式的限制，数学形态学不能很好地处理复杂的多边形轮廓化简，得到的结果往往很死板，适用范围比较小。

基于矢量数据的面要素合并综合算法大概有：基于Delaunay三角网邻近分析的多边形化简与合并算法，基于矩形几何的多边形差分组合及化简算法，基于ABTM（Agent技术与TIN技术、聚类技术）的多边形融合算法等。其中基于Delaunay三角网邻近分析的多边形化简与合并算法中提到的吸收式合并考虑的不够全面，又因一般情形下的弯曲骨架线是树结构，而不是线结构，且弯曲特征的宽度、深度分析尚有待完善，所以，缓冲夸大弯曲时，尚需寻求新的策略，以避免边界相交[1]；而基于矩形几何的多边形差分组合及化简算法适应形状轮廓矩形直角化的多边形，所以，其应用有一定的局限性；基于ABTM的多边形合并算法也有一些缺点，如只考虑了吸收式合并的情况，没有顾及合并过程中可能产生孔洞的情况，例如：建筑物中四合院中间有空地、湖泊中间都岛屿等。

基于上面的叙述与分析，该文提出了一种新的多边形融合算法，基于缓冲区操作的多边形融合算法，这种算法能最大程度地吸收已有算法的优点，避免他们存在的缺陷。

1 缓冲区融合多边形的原理

缓冲区操作是GIS领域中一种基础操作，几乎所有的GIS软件平台都包含此项功能，如图1所示，多边形的缓冲区操作可分正向操作，可以负向操作。正向操作时，图1（a）所示，多边形外环扩大，内环缩小，具有填平凹部，填补孔洞的特点；负向操作时，如图1（b）所示，效果跟正向完全相反；综合这两种操作，以相同半径，先正向后负向进行缓冲区操作，即双向缓冲区变换，得到结果如图1（c）所示，具有凸部不变，凹部缩小的特点。

该文借用双向缓冲区变换的特点，提出了一种利用缓冲区操作合并多边形的算法，原理如图2所示，多边形A和B融合的过程，实际上是求得两多边形中间“缝隙”的过程。将A和B视为一个整体多边形AB，则A和B之间的“缝隙”可看成整体多边形AB的凹部，利用双向缓冲区变换的特点，整体多边形AB进行缓冲半径L的双向缓冲区操作，得到缓冲区多边形C，多边形C减去原多边形A和多边形B，得到多边形“差”集，“差”集内的多边形有两种类型：普通凹部（多边形E）和缝隙（多边形F），普通凹部只于两个原多边形之一具有相接关系，依此将其剔除，得到“缝隙”F。最后，将缝隙多边形F、多变形A和多边形B合并，得到融合后的结果。

2 缓冲区融合多边形的算法设计

如图3所示，该文利用双向缓冲区操作融合多边形算法的具体步骤如下。

首先，根据基于距离的空间聚类算法，得到要融合的各个多边形集，假设其中一个多边形集合为S。

输入：多边形集S。

输出：多边形T。

步1：首先根据综合规则、地图比例尺、图形最小尺寸和双向缓冲区变换的特性来确定缓冲半径L的大小。

步2：取多边形X和Y，X∈S，Y∈S，將X和Y看成一个整体，进行缓冲半径L的双向缓冲区变换，得到缓冲区多边形Z。

步3：用多边形Z减去多边形X和Y，得到多边形“差”集Q，此“差”集Q中包含有两种多边形，即普通凹部多边形和缝隙多边形。

步4：依据“差”集Q中的多边形与原多边形的空间关系，去除普通凹部多边形，得到缝隙多边形集K`。设函数F（a，b），进行如下定义。

则缝隙集K为：

步5：取出多边形集S中符合步2条件的另一对多边形，替代X和Y，转到步2，直到多边形集A中所有多边形都被取到。得到总的缝隙集K，则转到步6。

步6：将步5中得到总的缝隙集K和输入的多边形集S进行多边形求并运算，得到合并的结果—多边形T。

需要注意的是，确定缓冲半径L时，应着重注意双向缓冲区变换的特性，将多边形之间的缝隙看成整体的凹部，设“缝隙”最窄处的距离D，根据实验效果分析，建议缓冲区半径L取D的1.5～3倍之间。

另外，在算法步3中，由于双向缓冲区变换填平凹陷的特性，很小的凹陷也会被填平，所以，在多边形求差运算之后，会产生一些很碎小的多边形，这些碎小的多边形对合并没有意思，却会在步4中进行判断，降低了算法的效率，可以以面积作为阈值排除碎小的多边形。

3 实验与分析

该文基于ArcGIS Engine 10.2二次开发组件，利用Visual Studio 2010软件开发平台进行二次开发，实现缓冲区变换多边形融合算法。为了测试算法的通用性，该文将不同组合的多边形融合统一放到一个实验数据中进行实验，实验结果如图4所示，从试验结果看，对于相离的不规则多边形，该文所提算法能够较好地将多边形融合到一起，得到的结果并保有原有多边形的排列形态。另外，由于双向缓冲区变换具有填补孔洞的性质，在多边形融合的过程中，如果原多边形本身具有的孔洞很小，也会自动被填补；再者，相较于其他算法，该文所提算法，可直接生成具有内环的多边形，不需要再附加其他处理动作。

由此可以看出，该文所提的利用缓冲区如何多边形算法非常适用于岛屿、池塘等地物的自动综合。不过，此算法目前还不能直接用于规则多边形的自动合并，如房屋的自动综合，如需使用，还需对缝隙进行直角化处理，这方面有待继续深入研究。

4 结语

该文基于缓冲区操作，充分利用了双向缓冲区变换的特点，提出了一种基于缓冲区变换的多边形合并算法。实验结果表明该方法能有效地自动合并相离的不规则多边形。该文所提的合并算法在规则的多边形合并方面还有待提高，如何利用缓冲区自动合并规则的多边形将是下一步研究的方向。

参考文献

[1] 艾廷华，郭仁忠，陈晓东.Delaunay三角网支持下的多边形融合与化简[J].中国图象图形学报，2001，6（7）：707-709.

[2] 艾廷华，郭仁忠.基于约束Delaunay结构的街道中轴线提取及网络模型建立[J].测绘学报，2000，29（4）：350-354.

[3] 艾廷华，郭仁忠.基于格式塔识别原则挖掘空间分布模式[J].测绘学报，2007，36（3）：303.

[4] 郭仁忠，艾廷华.制图综合中建筑物的合并与化简[J].武汉测绘科技大学学报，2000，25（1）：25-28.

[5] 毋河海.关于GIS中缓冲区的建立问题[J].武汉测绘科技大报，1997，22（4）：359-364.

[6] 陈学工，张文艺.一种GIS缓冲区矢量生成算法及实现[J].计算机技术与发展，2007，17（3）：240.

[7] 朱熀，艾廷华.基于条带扫描思想的线目标缓冲区快速构建[J].测绘学报，2006，35（2）：171-172.

[8] 毋河海.地图信息自动综合基本问题研究[J].武汉测绘大学报，2000，25（5）：381-383.

[9] 胡鹏，耿协鹏.图形的形态变换和地图代数凸壳算法[J].武汉大学学报，2005，30（11）：1003-1006.