楊秋菊 任海翔 孫進(jìn)冬 彭春暉

(江蘇省地質(zhì)測繪院, 江蘇 南京 211100)

0 引言

地理國情監(jiān)測是對全國陸地國土及毗鄰海域范圍內(nèi)地表覆蓋、重要地理要素變化情況監(jiān)測,形成現(xiàn)勢性強(qiáng)、精度高、全覆蓋的地理國情信息數(shù)據(jù)庫,服務(wù)于耕地種植狀況監(jiān)測、生態(tài)保護(hù)修復(fù)效果評價、督察執(zhí)法監(jiān)管以及自然資源管理宏觀分析等自然資源管理工作,并為各部門和地方政府提供地理國情信息決策支撐[1]。因此,控制地理國情監(jiān)測數(shù)據(jù)的質(zhì)量具有重要意義。而地理國情監(jiān)測的數(shù)據(jù)一般是按行政區(qū)劃分片生產(chǎn),導(dǎo)致在數(shù)據(jù)拼接時邊界處不可避免地會出現(xiàn)空間和屬性不一致的問題。此類問題通過人工接邊檢查的方式來解決,不僅耗時耗力,而且正確性難以保證。

目前,國內(nèi)存在地理國情監(jiān)測數(shù)據(jù)接邊檢查軟件,但大多都是基于ArcEngine平臺二次開發(fā)[2],使得軟件都依托于ArcGIS,執(zhí)行的效率較低。本文基于圖論在Microsoft Visual Studio 2019 編程環(huán)境下,實(shí)現(xiàn)了地理國情監(jiān)測數(shù)據(jù)的接邊算法,并在江蘇省宿遷市2020年地理國情監(jiān)測數(shù)據(jù)生產(chǎn)過程中驗(yàn)證了該方法的有效性,相比人工和ArcEngine平臺二次開發(fā)的軟件具有明顯的效率優(yōu)勢,并且在準(zhǔn)確性方面也能有很好的保障。

本次實(shí)驗(yàn)數(shù)據(jù)包含宿遷市宿城區(qū)、宿豫區(qū)、泗洪縣、泗陽縣、沭陽縣及徐州市新沂市6個區(qū)縣,面積約8 980 km2,地處江蘇省北部,南與淮安市毗連,東與連云港市接壤,北與邳州市相連,西與安徽省交界,處于徐、淮、連的中心地帶,以平原為主,河網(wǎng)密布。

1 基于圖論的算法思路

圖論(Graph Theory)也稱拓?fù)鋵W(xué),是由點(diǎn)和線構(gòu)成的拓?fù)浣Y(jié)構(gòu)。本文所用的算法的核心是依據(jù)歐拉定理構(gòu)建一個有效的平面圖(Planar Graph),即一個可靠的拓?fù)淇臻g結(jié)構(gòu),這個結(jié)構(gòu)必須滿足式(1)條件

V-E+F=2

(1)

式中,V為頂點(diǎn)數(shù);E為邊數(shù);F為被劃分區(qū)域數(shù)。

對于線(LineString)、面(Polygon)要素(面要素可以看成是首尾閉合的線要素),在線的起點(diǎn)與終點(diǎn)處,以及三交以上的節(jié)點(diǎn)處斷開,構(gòu)成由節(jié)點(diǎn)和線段組成的平面圖,同時創(chuàng)建幾何圖結(jié)構(gòu)(Geometry Graph Struct),有向邊結(jié)構(gòu)(Direct Edge Struct)和節(jié)點(diǎn)結(jié)構(gòu)(Node Struct),用來記錄邊界與圖形之間的關(guān)系。

如圖1所示,以線要素為例,存在線段A和B,構(gòu)建幾何圖時,A線段與B線段在節(jié)點(diǎn)N1處斷開成有向邊 c、d和e,生成節(jié)點(diǎn)N1、N2、N3和N4。

圖1 線要素平面圖

創(chuàng)建幾何圖結(jié)構(gòu)記錄各要素所包含的有向邊,結(jié)構(gòu)示例如下:

public class PlanarGraph///平面圖

{

public IEnumerable< DirectEdge > DirectEdges { get; } ///.Net迭代器,用以遍歷此平面圖中的全部有向邊

public IEnumerable< Node > Nodes { get; } ///.Net迭代器,用以遍歷此平面圖中的全部節(jié)點(diǎn)

public GeometryGraph[] Graphs { get; } ///存儲平面圖中全部幾何圖

}

public class GeometryGraph///幾何圖

{

public int ID { get; } ///圖形ID編號

public DirectEdge[] DirectEdges { get; } ///隸屬的有向邊數(shù)組

}

有向邊結(jié)構(gòu)記錄具體的坐標(biāo)數(shù)組,方向信息與隸屬信息,結(jié)構(gòu)示例如下:

public class DirectEdge ///有向邊

{

public Coordinate[]Coordinates { get; }///存儲有向邊具體的坐標(biāo)數(shù)組

public Direction[]Owners{ get; }///存儲擁有此有向邊的GeometryGraphID以及此GeometryGraph相對于有向邊的方向

public class Direction

{

public int ID { get;} ///圖形ID編號

public Direction Type {get;} ///圖形相對于DirectedEdge的方向

}

public enum Direction

{

Same,///方向與隸屬DirectedEdge相同

Different,///方向與隸屬DirectedEdge相反

}

}

節(jié)點(diǎn)結(jié)構(gòu)記錄具體的節(jié)點(diǎn)坐標(biāo),節(jié)點(diǎn)與邊界的關(guān)系,結(jié)構(gòu)示例如下:

public class Node///節(jié)點(diǎn)

{

public Coordinate Vertex { get; } ///存儲具體的節(jié)點(diǎn)坐標(biāo)信息

public DirectEdge[] DirectEdges { get; } ///存儲通過此節(jié)點(diǎn)的有向邊數(shù)組

}

要素的幾何坐標(biāo)信息只存取一次,減少了數(shù)據(jù)的冗余。通過兩張關(guān)系表記錄要素邊界之間的方向和關(guān)系,在接邊過程中,通過關(guān)系表即可方便地判斷出是否存在接邊要素,來達(dá)到接邊檢查的目的。

本算法與著名開源軟件Geos(Geometry Engine, Open Source)中的GeometryGraph有所不同,本算法中的拓?fù)淇臻g結(jié)構(gòu),不記錄Label(空間標(biāo)簽),只記錄邊線的方向。同時在構(gòu)建幾何圖過程中,添加了容差因子,使得構(gòu)建的幾何圖更具有包容性。

2 接邊檢查的方法實(shí)現(xiàn)

地理國情監(jiān)測數(shù)據(jù)一般以經(jīng)緯度坐標(biāo)系存儲,需將待檢查的數(shù)據(jù)轉(zhuǎn)換為平面投影坐標(biāo)系。

2.1 幾何接邊檢查

計算待查圖層的空間范圍(Extent),使用四叉樹(QuadTree)方法創(chuàng)建圖層空間索引,加快要素的檢索速度。地理國情監(jiān)測數(shù)據(jù)的生產(chǎn)一般按縣區(qū)劃分,接邊線是不規(guī)則的縣區(qū)界。

為了提高接邊檢查的效率,先以接邊線進(jìn)行空間查詢,獲取待查圖層中與當(dāng)前接邊線存在相交的要素。將接邊線和查詢出的相交要素融合在一起,共同構(gòu)建幾何圖P1。

2.2.1面要素檢查

(1)在幾何圖P1中篩選出隸屬于接邊線要素的有向邊,逐一遍歷該方向邊。

(2)對方向邊進(jìn)行判斷:若方向邊只隸屬于兩個待檢查面要素,且方向相反,則在該段位置上,圖形關(guān)系正確,存在接邊要素;若方向邊只隸屬于一個待檢查面要素,則在該段位置上,不存在接邊要素。

以圖2為例,面狀要素和接邊線一起構(gòu)建幾何圖,生成有向邊a、b…j。其中a至f為在接邊線上的有向邊,遍歷這些有向邊進(jìn)行檢查。判斷有向邊b在有向邊界表中同時隸屬于三個要素,接邊線、要素PA1和要素PA2,且方向?qū)傩韵喾?則可認(rèn)定在接邊線b處,存在需接邊要素,且接邊要素滿足接邊要求,接邊正確。同理接邊線d,也判定為接邊正確,但接邊線e,則只隸屬于兩個要素,接邊線和要素PB2,所以在接邊線e處,判定為未找到接邊要素,接邊有錯誤。

圖2 面狀要素接邊檢查

2.2.2線要素檢查

(1)在幾何圖P1中篩選出隸屬于接邊線要素的頂點(diǎn)(Vertex)。

(2)對頂點(diǎn)進(jìn)行判斷:若頂點(diǎn)隸屬于兩個或以上待檢查線要素,且方向相反,判斷隸屬的線要素是否在接邊線同一側(cè),若不是,則在該段位置上,圖形關(guān)系正確,存在接邊要素;若是,則在該段位置上,不存在接邊要素。若頂點(diǎn)只隸屬于一個待檢查線要素,則在該段位置上,不存在接邊要素。

以圖3為例,線狀要素和接邊線一起構(gòu)建平面圖,在接邊線上生成節(jié)點(diǎn)N1、N2…N5。遍歷接邊線上節(jié)點(diǎn),若節(jié)點(diǎn)只隸屬接邊線,則該處不存在待接邊線要素(節(jié)點(diǎn)N1和節(jié)點(diǎn)N5);若節(jié)點(diǎn)只隸屬于一個待接邊要素,則該處接邊存在錯誤(節(jié)點(diǎn)N4);若節(jié)點(diǎn)隸屬于二個及以上待接邊要素,則需判斷待接邊要素是否在接邊線一側(cè),在同一側(cè)的,接邊有可能錯誤(節(jié)點(diǎn)N3),列入可疑接邊問題人工核實(shí),不在同一側(cè)的為接邊正確。

圖3 線狀要素接邊檢查

2.2 屬性接邊檢查

屬性的接邊是建立在幾何接邊檢查正確的基礎(chǔ)上,根據(jù)檢查的要求,指定的屬性字段應(yīng)一致,判斷接邊線兩側(cè)要素屬性是否一致,若一致,則接邊正確;若不一致,則接邊存在錯誤。

3 生產(chǎn)應(yīng)用與效率對比

3.1 生產(chǎn)應(yīng)用

本文論述的接邊檢查方法,應(yīng)用于江蘇省宿遷市地理國情監(jiān)測項(xiàng)目,得到了很好的應(yīng)用價值。項(xiàng)目以區(qū)縣為單位生產(chǎn),接邊線為不規(guī)則的區(qū)縣界,接邊檢查程序讀取待接邊的兩個區(qū)縣和接邊線數(shù)據(jù),執(zhí)行完成,接邊檢查結(jié)果以MDB (Message Driven Bean)數(shù)據(jù)格式展示,可定位修改。

3.2 效率對比

為了驗(yàn)證本文論述接邊檢查方法的運(yùn)行效率優(yōu)勢和準(zhǔn)確性,選取了兩個區(qū)縣的地理國情數(shù)據(jù),人工設(shè)定接邊錯誤。將檢查人員分為三組進(jìn)行檢查,第一組安排一人,采用本文檢查程序檢查;第二組安排一人,采用某基于ArcEngine平臺程序檢查;第三組安排兩人,采用人工方式檢查。最后對檢查結(jié)果進(jìn)行比較分析,結(jié)果見表1。

表1 檢查結(jié)果對比

表1顯示,三種方法比較,本文方法可靠,在準(zhǔn)確率和效率上有明顯優(yōu)勢,能夠提高地理國情數(shù)據(jù)的生產(chǎn)效率,保證數(shù)據(jù)的質(zhì)量。

4 結(jié)束語

本文闡述了基于圖論的接邊算法思路,通過自主開發(fā)接邊程序?qū)崿F(xiàn)了地理國情數(shù)據(jù)的接邊檢查。該方法具有一定的普適性,能夠提高接邊檢查的準(zhǔn)確率和效率,對地理國情的生產(chǎn)具有較好的實(shí)用價值。但是,該方法仍有不足之處,檢查只能一次針對兩個接邊區(qū)縣;檢查的規(guī)則不能定制,無法只針對個別檢查項(xiàng)專查;檢查結(jié)果的存儲形式不方便作業(yè)人員修改;對于可疑的接邊點(diǎn),還需要人工判斷。下一步的工作重點(diǎn)是對檢查方法進(jìn)一步改進(jìn),減少人工的參與,完善程序的界面和定制化,使程序能夠操作簡便,適應(yīng)多樣化的需求。