利用緩沖區融合多邊形算法

周義軍

摘 要：多邊形融合是自動化制圖綜合中的重要步驟。目前，這類算法的設計主要基于多邊形幾何特征、拓撲特征進行分析，建立一種合適空間數據模型，以此來支持多邊形之間的臨近關系的探測。通過這種思路，該文提出了一種基于緩沖區操作的多邊形融合的算法，利用現有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.