土地利用圖斑自動檢測算法研究

程建燕，康建榮，周 棒，胡宗楠

(江蘇師范大學，江蘇 徐州 221116)

0 引 言

土地利用現(xiàn)狀圖是指以地圖的形式反映不同行政區(qū)內(nèi)的土地利用類型、利用現(xiàn)狀以及與社會、自然關系等的專題地圖，土地利用圖斑的自動綜合需要考慮拓撲關系、空間關系和語義關系等多方面因素[1]。在土地利用現(xiàn)狀圖制圖綜合過程中，因多邊形幾何形狀的化簡會導致原有圖斑拓撲關系的破壞，因小面積圖斑聚集分布會導致原有圖斑空間關系的破壞，因此圖斑自動檢測成為十分重要的部分。在圖斑的自動檢測過程中涉及到的空間沖突主要是任意相鄰圖斑多邊形間間距過小導致產(chǎn)生“橋梁區(qū)域”無法分辨[2]，以及小面積圖斑過多、局部圖斑密集導致需要進行圖斑合并的問題。針對此問題，眾多國內(nèi)外學者對圖斑自動檢測進行了相應的研究。比較有代表性的研究成果有如下幾類：艾廷華等根據(jù)圖斑合并算子進行圖斑的聚合和融合[3]，劉耀林等提出了基于本體的土地利用數(shù)據(jù)綜合研究[4]，郭慶勝等研究了圖斑合并的漸進式方法研究[5]，楊志龍?zhí)岢隽嘶谙伻核惴ǖ膱D斑合并方法[6]，但是這些研究大多是對符合合并規(guī)則的圖斑進行合并 很少涉及鄰近圖斑間產(chǎn)生的間隙問題。還有一些學者從顧及鄰域變化的角度提出圖斑群合并的方法，如翁杰提出了顧及鄰域變化下的圖斑群合并方法[7]，李成名提出了鄰域關系維持下的狹長圖斑分解方法[8]，李英提出了語義與空間相結合下的圖斑自動綜合模型[9]。但是這些研究未能很好地維持同地類圖斑間的拓撲鄰近關系，保持圖斑的自然形態(tài)結構。文中從計算幾何的角度，基于公共邊界提出一種解決圖斑合并的算法。該算法能夠分辨圖斑間間隙，消除鄰近圖斑間的“橋梁區(qū)域”，較好地維持地類圖斑間的拓撲關系，保持圖斑的自然彎曲形態(tài)，并結合Weiler-Atherton算法，刪除小面積圖斑，優(yōu)化圖斑群自動合并效果。

1 圖斑檢測基礎定義

土地利用現(xiàn)狀圖制圖綜合過程中圖斑檢測的對象主要有兩類[6]：一是距離過近導致在圖中不易分辨的圖斑；二是面積過小導致在圖中過于密集的圖斑。針對這兩類圖斑，定義了兩種操作即“橋梁區(qū)域”檢測和圖斑自動合并?！皹蛄簠^(qū)域”是指具有鄰近關系的圖斑多邊形間間距過小產(chǎn)生的狹窄縫隙，它會導致在圖中無法分辨，引起重疊、縫隙等空間沖突，如圖1所示。當兩圖斑多邊形具有公共邊界時，在拓撲關系上視為鄰近；當兩圖斑多邊形在拓撲關系上相離，但相互間的距離非常小且難以區(qū)分時，視為鄰近[10-11]?！皹蛄簠^(qū)域”檢測融入距離關系、拓撲關系，檢測并消除相鄰圖斑多邊形間的間隙，保持圖斑間的鄰近關系。圖斑自動合并主要是對小面積圖斑進行處理，減少土地利用現(xiàn)狀圖中密集圖斑的數(shù)量，使地類圖斑變得簡潔。圖斑自動合并會導致圖斑的消失，消失的圖斑的拓撲包含關系和鄰近關系全部由合并后的大圖斑繼承，因此圖斑自動合并是在與消失的圖斑具有拓撲包含關系和鄰近關系的圖斑中進行[12-14]。

2 圖斑自動檢測方法分析

2.1 圖斑多邊形“橋梁區(qū)域”檢測

2.1.1 圖斑多邊形公共邊界

在進行矢量化土地利用現(xiàn)狀圖的過程中，圖斑多邊形可能出現(xiàn)自相交區(qū)域。自相交是指圖斑多邊形所有邊之間除了頂點外還存在相交的邊的情況[15]。這需要對土地利用圖斑進行自相交檢測判斷，檢測算法按照文獻[16]中的算法設計，對于自相交區(qū)域采用直接刪除的方式來進行處理。

圖斑多邊形看作是封閉的多線段，以邊界線段操作為核心求解多邊形的交點。利用射線交點法[17-18]進行點與多邊形的關系確定，即待判定點為起點作射線，根據(jù)射線與多邊形邊界交點的奇偶數(shù)，確定是否點在多邊形內(nèi)部。若交點數(shù)為奇數(shù)，則點在多邊形內(nèi)；若交點數(shù)為偶數(shù)，則在多邊形外。通過點與多邊形的關系，進而判斷多邊形間的相互關系。若沒有交點，則為包含關系或相離關系；若有交點，則為交叉關系。包含和分離關系的判定實質(zhì)是若頂點都在多邊形內(nèi)部，則是包含關系；若頂點都在多邊形外部，則是分離關系。

f=(xn+1-xn)(y-yn)-(yn+1-yn)(x-xn),

n=j或k

(1)

f1=(xn+1-xn)(yj-yn)-(yn+1-yn)(xj-xn),

n=k

(2)

2.1.2 “橋梁區(qū)域”檢測方法

圖斑多邊形求取公共邊界后，相鄰圖斑多邊形基于公共邊界進行“橋梁區(qū)域”自動檢測及消除。結合圖斑多邊形的數(shù)據(jù)結構，圖斑多邊形的頂點序列可分為順時針或逆時針方向排列。因此，相鄰圖斑間的“橋梁區(qū)域”可分為多種情況，即由公共邊界出發(fā)，鄰近兩圖斑的頂點序列皆按同方向排列時產(chǎn)生的“橋梁區(qū)域”形態(tài)存在差別，并當相鄰圖斑多邊形頂點序列按相反方向排列時產(chǎn)生的“橋梁區(qū)域”也大不相同，具體情況如圖3所示。

設相鄰圖斑多邊形間的頂點距離為length，兩頂點間的距離閾值為λ。圖斑多邊形M，C進行求交后，基于公共邊界分別以同方向遍歷相鄰圖斑多邊形頂點，在交點處結束遍歷。當相鄰圖斑多邊形間的頂點距離lengthλ時，則取對應兩頂點的中點μ代替原圖斑多邊形頂點，形成新的共享邊界，消除原圖斑間的“橋梁區(qū)域”。圖斑多邊形僅僅在同一方向檢查“橋梁區(qū)域”不滿足所有圖斑多邊形的情況，在相鄰圖斑頂點排列方向存在差異時，會產(chǎn)生不同形態(tài)的“橋梁區(qū)域”。此算法基于公共邊界改變圖斑多邊形頂點的排列順序，能夠進行多種情況的檢查，對相鄰圖斑多邊形進行全面的“橋梁區(qū)域”檢測。運用此算法進行模擬實驗，實驗結果如圖4所示。

圖2 公共邊界求取結果

圖3 橋梁區(qū)域分類

圖4 橋梁區(qū)域檢測結果

2.2 圖斑自動合并算法

相鄰圖斑多邊形求交后，結合Weiler-Atherton算法[19-22]，采用鏈表的形式判斷交點的“入出性”，進而實現(xiàn)圖斑的自動合并。兩多邊形相交時，交點必然成對出現(xiàn)。根據(jù)圖斑多邊形之間的關系，判斷交點的“入出性”：一個多邊形進入另一多邊形的交點，稱為“入點”；一個多邊形離開另一多邊形的交點，稱為“出點”。由多邊形的某個“出點”進行遍歷，碰到出點，則沿著此多邊形順時針方向記錄頂點序列，并將“出點”的flag記號刪除，以免重復。遇到“入點”時，則沿著另一多邊形逆時針方向記錄頂點序列。按照此規(guī)則，如此交替地沿著兩個多邊形的邊界進行遍歷，直到回到起始點為止，將所有的出點搜集完畢后則算法結束。由于圖斑合并需要考慮到地類等因素的影響，此算法只對于同屬于同一地類的圖斑進行合并。

以Region_Line_3D鏈表結構來構建相鄰圖斑多邊形M、C，相鄰圖斑多邊形M、C的頂點序列按照順時針方向排列。求取相鄰圖斑多邊形M、C的交點，對交點相同的點進行統(tǒng)一命名，并將交點按位置順序分別插入鏈表M、C中。根據(jù)多邊形M、C的頂點與交點所形成的邊界的中點，由Weiler-Atherton合并算法思想，進行判別多邊形M、C中交點的“入出性”。若邊界中點在另一圖斑區(qū)域外，則此交點為“入點”；若邊界中點在另一圖斑區(qū)域內(nèi)，則此交點為“出點”。初始化多邊形鏈表line，尋找圖斑多邊形鏈表中的“出點”，將“出點”記錄到line中，并將“出點”標記flag刪除。沿著一圖斑多邊形M順序取其頂點，如果頂點不是“入點”，則將其頂點記錄到line中，否則沿著另一圖斑多邊形C行進。當多邊形C中頂點不是“出點”時，將其頂點記錄到line中，否則流程轉(zhuǎn)至上一步多邊形M中行進。判斷找到的最后一點是否為起點，若為起點則形成合并圖斑區(qū)域line，查找結束。當相鄰圖斑多邊形沒有交點且為包含關系時，直接刪除小圖斑，其拓撲關系和權屬關系由包含的大圖斑繼承。具體流程如圖5所示。

圖5 圖斑合并流程

3 應用實例

3.1 程序?qū)崿F(xiàn)設計

文中將整個程序應用于整幅土地利用圖中，{Polygon}={P1,P2,…,Pn}為土地利用圖中所有的圖斑集合,對于{Polygon}中的任一圖斑Pi都獲取其x，y坐標的最大值maxx,maxy和最小值minx,miny，形成一個包圍此圖斑的擴展矩形區(qū)域。檢測{Polygon}中其余圖斑Pj的矩形區(qū)域與Pi矩形區(qū)域是否有交集Ψ，若Ψ>0,則記錄Pj的所屬地類名稱Name(Pj)和圖斑數(shù)據(jù)集合PD{Pj}。對Pi和PD{Pj}進行“橋梁區(qū)域”檢測和圖斑自動合并，合并時將Name(Pj)中與Pi不屬于同一地類的圖斑剔除，遍歷完整個圖斑集合{Polygon}，實現(xiàn)整幅土地利用圖的圖斑自動合并。

整個程序以存儲在*.txt文件中的圖斑坐標數(shù)據(jù)為研究對象，按照圖斑數(shù)據(jù)準備、圖斑數(shù)據(jù)檢測合并和土地利用結果圖輸出的流程設計，在考慮不同地類間圖斑不進行合并的情況下，對土地利用現(xiàn)狀圖上的大批量圖斑進行“橋梁區(qū)域”的檢測和圖斑合并，主要實現(xiàn)土地利用現(xiàn)狀圖中圖斑間的無縫隙、無重疊和小圖斑的刪除與合并。整個程序借助C++語言和MFC控制平臺進行操作，并將輸出結果在Auto CAD軟件中進行可視化顯示，使得整個程序方便、快捷，便于數(shù)據(jù)的重復性操作。程序的實現(xiàn)流程如圖6所示。

圖6 程序?qū)崿F(xiàn)流程

3.2 實例驗證

文中采用的實驗數(shù)據(jù)為山西省第三次全國國土調(diào)查中的土地資源業(yè)務數(shù)據(jù)，如圖7所示。該圖中因圖斑多邊形疊置時圖斑邊界不一致，產(chǎn)生大量縫隙和重疊，導致鄰近圖斑間產(chǎn)生“橋梁區(qū)域”無法識別，破壞了土地利用現(xiàn)狀圖的全覆蓋、無縫隙特點。并且圖中小面積圖斑過多，局部圖斑密集，不利于圖斑的自動綜合。利用文中算法，并根據(jù)第三次全國國土調(diào)查實施方案的要求[23]，采用最小上圖面積需大于200 m2的規(guī)范對此土地利用現(xiàn)狀圖進行“橋梁區(qū)域”檢測和圖斑的自動合并，經(jīng)此算法處理后的結果如圖8所示。

圖7 數(shù)據(jù)原圖

圖8 處理結果

3.3 結果分析

土地利用現(xiàn)狀圖的圖斑檢測算法中對于小面積圖斑的處理，其處理后的結果需要通過各類用地面積的相對平衡進行評價[24-26]。由表1可以看出，土地利用圖斑檢測前后總的圖斑面積保持相對平衡，總的圖斑數(shù)量相比檢測前明顯減少。其中農(nóng)用地、建設用地和未利用地的圖斑數(shù)量相比較于檢測前均減少一半，檢測后的農(nóng)用地圖斑面積相對于之前有明顯增加，建設用地和未利用地的圖斑面積相比較于之前明顯減少。土地利用現(xiàn)狀圖經(jīng)圖斑檢測算法后不僅“橋梁區(qū)域”問題得到解決，而且圖中的小圖斑密集區(qū)域也明顯減少。由圖8可以看出，此土地利用現(xiàn)狀圖中圖斑間的“橋梁區(qū)域”能夠被自動檢測且修復，從而消除了此圖中圖斑間的縫隙和重疊區(qū)域，保證了土地利用現(xiàn)狀圖中全覆蓋、無重疊、無縫隙的特點，并且從圖中也能明顯看出面積過小的圖斑能夠自動合并到同地類的大圖斑之中，將原始的小圖斑從圖斑數(shù)據(jù)中刪除，減少了密集區(qū)域的圖斑數(shù)量。結果表明，此算法能夠完全自動化地實現(xiàn)小圖斑的自動合并，保持地類的繼承性，彌補了ArcGIS軟件中需要人工主觀判斷的缺陷，并能夠?qū)︵徑鼒D斑間的“橋梁區(qū)域”實現(xiàn)快速的檢測和消除，維持土地利用圖斑原有的自然彎曲形態(tài)，提高制圖綜合的效率。

表1 土地利用現(xiàn)狀圖檢測前后對比

4 結束語

文中采用自相交區(qū)域直接刪除的算法對土地利用圖斑多邊形進行自相交預處理后，通過定義求交規(guī)則的方式求取土地利用圖斑多邊形之間的公共邊界?；卩徑鼒D斑間的公共邊界以多邊形鏈表的結構并按照一定方向遍歷土地利用圖斑，在維持圖斑拓撲一致性的基礎上，檢測并消除圖斑間間距過小的“橋梁區(qū)域”。

該算法依據(jù)交點所在邊界的中點，實現(xiàn)圖斑多邊形間關系判斷。同時利用Weiler-Atherton算法，判定邊界中點是否在另一圖斑區(qū)域的內(nèi)部，進行交點的入出性判斷。并根據(jù)最小上圖面積的原則，在圖斑群中進行小面積圖斑的搜索，在保持地類圖斑間的繼承關系的基礎上批量消除小面積圖斑，實現(xiàn)圖斑的自動合并。

對于第三次國土調(diào)查中的批量圖斑數(shù)據(jù)，整個制圖綜合過程只需要一幅土地利用現(xiàn)狀圖的圖斑坐標數(shù)據(jù)，簡化了計算過程，快速有效地實現(xiàn)了鄰近圖斑間的“橋梁區(qū)域”檢測改正和小圖斑群的自動合并，解決了ArcGIS軟件中存在的制圖工具功能簡單、自動化程度不高等問題，提高了土地利用現(xiàn)狀圖的制圖效率。