利用緩沖區(qū)融合多邊形算法

周義軍

摘 要：多邊形融合是自動化制圖綜合中的重要步驟。目前，這類算法的設(shè)計主要基于多邊形幾何特征、拓?fù)涮卣鬟M(jìn)行分析，建立一種合適空間數(shù)據(jù)模型，以此來支持多邊形之間的臨近關(guān)系的探測。通過這種思路，該文提出了一種基于緩沖區(qū)操作的多邊形融合的算法，利用現(xiàn)有GIS系統(tǒng)普遍具有的緩沖區(qū)操作功能，進(jìn)行合理的設(shè)計，從而達(dá)到多邊形融合的效果。

關(guān)鍵詞：多邊形融合 正向緩沖區(qū)操作 負(fù)向緩沖區(qū)操作 雙向緩沖區(qū)變換

中圖分類號：P208 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2017）03（c）-0054-03

多邊形融合算法在地圖綜合領(lǐng)域起著非常重要的作用，就目前來看，方法主要可為兩類，基于柵格結(jié)構(gòu)的算法和基于矢量數(shù)據(jù)的算法。

基于柵格結(jié)構(gòu)的算法中，典型方法是應(yīng)用數(shù)學(xué)形態(tài)學(xué)原理來實施多邊形化簡與合并，利于數(shù)學(xué)方法對圖像進(jìn)行膨脹、腐蝕、開運算、閉運算、集中、薄化和厚化等運算，算法速度與區(qū)域面積有關(guān)，區(qū)域圖像越大計算量越大，綜合質(zhì)量依賴于硬件設(shè)備，另受模板結(jié)構(gòu)和樣式的限制，數(shù)學(xué)形態(tài)學(xué)不能很好地處理復(fù)雜的多邊形輪廓化簡，得到的結(jié)果往往很死板，適用范圍比較小。

基于矢量數(shù)據(jù)的面要素合并綜合算法大概有：基于Delaunay三角網(wǎng)鄰近分析的多邊形化簡與合并算法，基于矩形幾何的多邊形差分組合及化簡算法，基于ABTM（Agent技術(shù)與TIN技術(shù)、聚類技術(shù)）的多邊形融合算法等。其中基于Delaunay三角網(wǎng)鄰近分析的多邊形化簡與合并算法中提到的吸收式合并考慮的不夠全面，又因一般情形下的彎曲骨架線是樹結(jié)構(gòu)，而不是線結(jié)構(gòu)，且彎曲特征的寬度、深度分析尚有待完善，所以，緩沖夸大彎曲時，尚需尋求新的策略，以避免邊界相交[1]；而基于矩形幾何的多邊形差分組合及化簡算法適應(yīng)形狀輪廓矩形直角化的多邊形，所以，其應(yīng)用有一定的局限性；基于ABTM的多邊形合并算法也有一些缺點，如只考慮了吸收式合并的情況，沒有顧及合并過程中可能產(chǎn)生孔洞的情況，例如：建筑物中四合院中間有空地、湖泊中間都島嶼等。

基于上面的敘述與分析，該文提出了一種新的多邊形融合算法，基于緩沖區(qū)操作的多邊形融合算法，這種算法能最大程度地吸收已有算法的優(yōu)點，避免他們存在的缺陷。

1 緩沖區(qū)融合多邊形的原理

緩沖區(qū)操作是GIS領(lǐng)域中一種基礎(chǔ)操作，幾乎所有的GIS軟件平臺都包含此項功能，如圖1所示，多邊形的緩沖區(qū)操作可分正向操作，可以負(fù)向操作。正向操作時，圖1（a）所示，多邊形外環(huán)擴大，內(nèi)環(huán)縮小，具有填平凹部，填補孔洞的特點；負(fù)向操作時，如圖1（b）所示，效果跟正向完全相反；綜合這兩種操作，以相同半徑，先正向后負(fù)向進(jìn)行緩沖區(qū)操作，即雙向緩沖區(qū)變換，得到結(jié)果如圖1（c）所示，具有凸部不變，凹部縮小的特點。

該文借用雙向緩沖區(qū)變換的特點，提出了一種利用緩沖區(qū)操作合并多邊形的算法，原理如圖2所示，多邊形A和B融合的過程，實際上是求得兩多邊形中間“縫隙”的過程。將A和B視為一個整體多邊形AB，則A和B之間的“縫隙”可看成整體多邊形AB的凹部，利用雙向緩沖區(qū)變換的特點，整體多邊形AB進(jìn)行緩沖半徑L的雙向緩沖區(qū)操作，得到緩沖區(qū)多邊形C，多邊形C減去原多邊形A和多邊形B，得到多邊形“差”集，“差”集內(nèi)的多邊形有兩種類型：普通凹部（多邊形E）和縫隙（多邊形F），普通凹部只于兩個原多邊形之一具有相接關(guān)系，依此將其剔除，得到“縫隙”F。最后，將縫隙多邊形F、多變形A和多邊形B合并，得到融合后的結(jié)果。

2 緩沖區(qū)融合多邊形的算法設(shè)計

如圖3所示，該文利用雙向緩沖區(qū)操作融合多邊形算法的具體步驟如下。

首先，根據(jù)基于距離的空間聚類算法，得到要融合的各個多邊形集，假設(shè)其中一個多邊形集合為S。

輸入：多邊形集S。

輸出：多邊形T。

步1：首先根據(jù)綜合規(guī)則、地圖比例尺、圖形最小尺寸和雙向緩沖區(qū)變換的特性來確定緩沖半徑L的大小。

步2：取多邊形X和Y，X∈S，Y∈S，將X和Y看成一個整體，進(jìn)行緩沖半徑L的雙向緩沖區(qū)變換，得到緩沖區(qū)多邊形Z。

步3：用多邊形Z減去多邊形X和Y，得到多邊形“差”集Q，此“差”集Q中包含有兩種多邊形，即普通凹部多邊形和縫隙多邊形。

步4：依據(jù)“差”集Q中的多邊形與原多邊形的空間關(guān)系，去除普通凹部多邊形，得到縫隙多邊形集K`。設(shè)函數(shù)F（a，b），進(jìn)行如下定義。

則縫隙集K為：

步5：取出多邊形集S中符合步2條件的另一對多邊形，替代X和Y，轉(zhuǎn)到步2，直到多邊形集A中所有多邊形都被取到。得到總的縫隙集K，則轉(zhuǎn)到步6。

步6：將步5中得到總的縫隙集K和輸入的多邊形集S進(jìn)行多邊形求并運算，得到合并的結(jié)果—多邊形T。

需要注意的是，確定緩沖半徑L時，應(yīng)著重注意雙向緩沖區(qū)變換的特性，將多邊形之間的縫隙看成整體的凹部，設(shè)“縫隙”最窄處的距離D，根據(jù)實驗效果分析，建議緩沖區(qū)半徑L取D的1.5～3倍之間。

另外，在算法步3中，由于雙向緩沖區(qū)變換填平凹陷的特性，很小的凹陷也會被填平，所以，在多邊形求差運算之后，會產(chǎn)生一些很碎小的多邊形，這些碎小的多邊形對合并沒有意思，卻會在步4中進(jìn)行判斷，降低了算法的效率，可以以面積作為閾值排除碎小的多邊形。

3 實驗與分析

該文基于ArcGIS Engine 10.2二次開發(fā)組件，利用Visual Studio 2010軟件開發(fā)平臺進(jìn)行二次開發(fā)，實現(xiàn)緩沖區(qū)變換多邊形融合算法。為了測試算法的通用性，該文將不同組合的多邊形融合統(tǒng)一放到一個實驗數(shù)據(jù)中進(jìn)行實驗，實驗結(jié)果如圖4所示，從試驗結(jié)果看，對于相離的不規(guī)則多邊形，該文所提算法能夠較好地將多邊形融合到一起，得到的結(jié)果并保有原有多邊形的排列形態(tài)。另外，由于雙向緩沖區(qū)變換具有填補孔洞的性質(zhì)，在多邊形融合的過程中，如果原多邊形本身具有的孔洞很小，也會自動被填補；再者，相較于其他算法，該文所提算法，可直接生成具有內(nèi)環(huán)的多邊形，不需要再附加其他處理動作。

由此可以看出，該文所提的利用緩沖區(qū)如何多邊形算法非常適用于島嶼、池塘等地物的自動綜合。不過，此算法目前還不能直接用于規(guī)則多邊形的自動合并，如房屋的自動綜合，如需使用，還需對縫隙進(jìn)行直角化處理，這方面有待繼續(xù)深入研究。

4 結(jié)語

該文基于緩沖區(qū)操作，充分利用了雙向緩沖區(qū)變換的特點，提出了一種基于緩沖區(qū)變換的多邊形合并算法。實驗結(jié)果表明該方法能有效地自動合并相離的不規(guī)則多邊形。該文所提的合并算法在規(guī)則的多邊形合并方面還有待提高，如何利用緩沖區(qū)自動合并規(guī)則的多邊形將是下一步研究的方向。

參考文獻(xiàn)

[1] 艾廷華，郭仁忠，陳曉東.Delaunay三角網(wǎng)支持下的多邊形融合與化簡[J].中國圖象圖形學(xué)報，2001，6（7）：707-709.

[2] 艾廷華，郭仁忠.基于約束Delaunay結(jié)構(gòu)的街道中軸線提取及網(wǎng)絡(luò)模型建立[J].測繪學(xué)報，2000，29（4）：350-354.

[3] 艾廷華，郭仁忠.基于格式塔識別原則挖掘空間分布模式[J].測繪學(xué)報，2007，36（3）：303.

[4] 郭仁忠，艾廷華.制圖綜合中建筑物的合并與化簡[J].武漢測繪科技大學(xué)學(xué)報，2000，25（1）：25-28.

[5] 毋河海.關(guān)于GIS中緩沖區(qū)的建立問題[J].武漢測繪科技大報，1997，22（4）：359-364.

[6] 陳學(xué)工，張文藝.一種GIS緩沖區(qū)矢量生成算法及實現(xiàn)[J].計算機技術(shù)與發(fā)展，2007，17（3）：240.

[7] 朱熀，艾廷華.基于條帶掃描思想的線目標(biāo)緩沖區(qū)快速構(gòu)建[J].測繪學(xué)報，2006，35（2）：171-172.

[8] 毋河海.地圖信息自動綜合基本問題研究[J].武漢測繪大學(xué)報，2000，25（5）：381-383.

[9] 胡鵬，耿協(xié)鵬.圖形的形態(tài)變換和地圖代數(shù)凸殼算法[J].武漢大學(xué)學(xué)報，2005，30（11）：1003-1006.