網(wǎng)格化河湖管理中的地理實體編碼與匹配

蔡赟 呂景旭

摘要 網(wǎng)格化管理由于其可以保證地理實體的完整性、管理的便捷性等優(yōu)勢，在河湖數(shù)據(jù)管理中得到廣泛的應用。傳統(tǒng)編碼方案基于矩形或經(jīng)緯網(wǎng)的分幅方法，對地理實體位置信息的表達不適用于網(wǎng)格化管理。本文針對河湖數(shù)據(jù)網(wǎng)格化管理，在研究相關編碼方案的基礎上，基于四進制Morton碼的編碼思想，對常規(guī)線性四叉樹存在的一些弊端進行改進，設計了一種基于地理實體位置信息的編碼方案，所設計方案提高了空間利用率與查詢效率，便于河湖數(shù)據(jù)的維護與更新。

關鍵詞網(wǎng)格化;地理實體編碼;四叉樹;Morton碼

1引言

在地學領域中，網(wǎng)格化是一種依照道路、水系、行政區(qū)劃邊界等要素對地理空間進行劃分的方法[1]。劃分形成的多邊形稱為網(wǎng)格單元，各個網(wǎng)格單元相互鄰接且不發(fā)生交叉，其間的空間關系是隱含表達的[2]。與傳統(tǒng)分幅方式相比，網(wǎng)格化可以最大限度地保證地理要素的完整性與連續(xù)性。在數(shù)據(jù)處理中，可減少接邊的工作量，提高工作效率，在實際應用中方便日常管理，因此在河湖數(shù)據(jù)管理中得到了廣泛應用。

2編碼方法

2.1四叉樹與Morton碼地址編碼

四叉樹是一種應用十分廣泛的數(shù)據(jù)結構[5]，它的建立是將地理空間劃分為四個相等的子空間，然后通過遞歸的方式對子空間重復劃分直至滿足一定要求后停止，劃分后對應的格網(wǎng)信息存儲在葉結點中，位置信息則隱含于結點編號（即地址編碼）中。Morton碼通過將二進制的行號和列號交叉組合為格網(wǎng)賦予地址編碼。相比于其他編碼方案中直接記錄四叉樹行列號的方式[3]，四進制Morton碼將二維數(shù)據(jù)轉為一維數(shù)據(jù)，同時將空間層次包含在編碼中，更有利于數(shù)據(jù)結構的設計以及存儲。

當?shù)乩韺嶓w位置分布較為均勻時，四叉樹各個分支之間較為平衡，數(shù)據(jù)插入和查詢都有較高的效率;而當數(shù)據(jù)量較大且分布不均時，隨著數(shù)據(jù)的逐漸插入，不均衡的數(shù)據(jù)分布將導致四叉樹各分支之間失去平衡。由于存儲實體的結點均為葉結點，中間結點與根結點均不參與存儲，檢索時必須遍歷至葉結點才能結束，這樣就會增加檢索深度，降低檢索的效率，同時造成存儲空間的浪費。

因此，本文在建立四叉樹時，將地理實體信息存儲在完全包含該實體的最低層次結點中，而不是完全存儲在葉結點中。這樣改變存儲位置之后，根結點、中間結點就與葉結點一樣，需要使用四進制Morton碼來獲取地址編碼。改進前后的四叉樹以及Morton碼的應用如圖1、表1所示（根結點代表第0層）：

以實體C為例，該實體涉及第2層的結點00與結點02，但由于結點00、01、02、03為第一層的同一結點的子結點，故檢索區(qū)域包含2*2個結點，在使用單層Morton碼時，對應的區(qū)域邊長值為2，在四叉樹中檢索至樹的第2層獲取到相關實體，需要用2個結點來存儲實體信息。而在使用分層Morton碼時，包含實體C的最小格網(wǎng)為以上四個結點的父結點，處于四叉樹中第1層，對應的分層Morton碼為00，僅需1個結點存儲，檢索時遍歷至樹的第1層即可結束。由以上對比易知，改進后的分層Morton碼以及四叉樹充分利用了現(xiàn)有結點，節(jié)約了存儲空間，同時降低了涉及范圍較廣的實體的檢索深度，提高了檢索效率。

2.2 格網(wǎng)劃分與編碼

格網(wǎng)的劃分與編碼設計基于2.1中分層Morton編碼的基本思想進行。由于四進制分層Morton碼的長度與所在層次相關，為保證碼段長度恒定，當碼段長度空缺時使用“9”進行補位。如圖2，編碼由四部分組成，前三部分為不同層次的位置碼段，分別為行政區(qū)劃位置碼（5位）、網(wǎng)格單元位置碼（4位）、實體位置碼（7位），最后一部分為擴展碼（2位）。

第一部分為行政區(qū)劃位置碼，通過對根結點存儲的地理空間劃分2次，最終劃分為3層，第2層的結點共16個，政區(qū)實體存儲在四叉樹中0、1、2層，碼段長度為5位，其中Morton碼3位，順序碼2位（表示市級行政編號）。

第二部分為網(wǎng)格單元位置碼，在第一次劃分的基礎上對地理空間再劃分2次，空間總共被劃分為5層，網(wǎng)格單元主要存儲在四叉樹中3、4層，第4層的結點共256個，碼段長度為6位，其中Morton碼4位，順序碼2位（表示網(wǎng)格單元編號）。

第三部分為實體位置碼，在第二次劃分的基礎上再劃分4次，至此，空間總共被劃分為9層，地理實體主要存儲在四叉樹中5、6、7、8層，葉結點共65536個，碼段長度為11位，其中Morton碼8位，順序碼3位（地理實體編號，保證地理實體的唯一性）。

第四部分的擴展碼默認為“00”，方便數(shù)據(jù)的存儲與管理。

同時，為避免編碼長度過長，數(shù)據(jù)表中將前兩個碼段與后兩個碼段分別存儲在兩個字段中。這樣，基于分層思想的編碼方式，將地理實體位置信息通過四進制Morton碼將空間索引記錄在編碼中，為地理實體的快速檢索提供了依據(jù)。

3地理實體檢索與匹配

在網(wǎng)格化河湖管理系統(tǒng)中，根據(jù)編碼可實現(xiàn)未知地理實體與數(shù)據(jù)庫中地理實體的初步匹配。日常管理中，網(wǎng)格單元由專門的巡查人員進行巡查，發(fā)現(xiàn)異常時將信息進行上報。服務器端可根據(jù)巡查人員位置以及上報的實體信息自動生成地理實體位置相關碼段。依照生成的位置碼段，與數(shù)據(jù)庫中的實體進行編碼匹配，最終將檢索范圍限制在包含該實體的最小四叉樹網(wǎng)格內(nèi)。圖3中（a）（b）分別為江蘇省和南京市的格網(wǎng)劃分與Morton編碼，表2為江蘇省部分市區(qū)的行政區(qū)劃位置碼：

如圖3（a）中所示，通過兩次劃分將江蘇省所處空間分為3層，各地級市根據(jù)其空間位置存儲在不同層次的結點中，如完全包含南京市的最小結點為第2層中Morton碼003的結點，依據(jù)其行政區(qū)劃代碼3201得到順序碼為01，最終得到南京的行政區(qū)劃位置碼為00301。同理可得，完全包含蘇州的最小結點為第1層中Morton碼01的結點，其行政區(qū)劃位置碼為01905;揚州處在第1次劃分的分割線上，只有根結點可完全包含該政區(qū)實體，因此其行政區(qū)劃位置碼為09910。圖中根據(jù)巡查人員所處A點位置信息，依照點與多邊形關系判斷出該巡查員位于南京市范圍內(nèi)，因此自動生成行政區(qū)劃碼段為00301。確定行政區(qū)劃范圍之后，如圖3（b）所示，在003結點的基礎上通過同樣的方法繼續(xù)進行格網(wǎng)劃分和位置關系判定，可以自動生成網(wǎng)格單元位置編碼為129914（位置關系判定得到所處網(wǎng)格單元順序碼為14）。在確定網(wǎng)格單元的基礎上，根據(jù)上報的地理實體位置信息，可知包含該實體的最小四叉樹結點位于四叉樹中第5層，Morton碼為21999，因此生成的實體編碼為21999999000（順序碼默認為000）。至此便可獲得上報地理實體編碼為“003011299141299999900000”，進而在數(shù)據(jù)庫中通過編碼匹配篩選出符合條件的實體進行進一步匹配。

通過編碼篩選之后只有很少的地理實體進入候選集，可大大減少與待匹配的實體進行精確匹配的時間。在河湖數(shù)據(jù)中，點狀實體多為水利設施，在空間分布上較為分散，可通過計算點實體間的曼哈頓距離完成匹配;線狀實體多為單線河、航道數(shù)據(jù)等，可依次通過計算長度偏差、首點終點連線的方向偏差進一步縮小檢索范圍，最終通過計算Hausdorff距離實現(xiàn)精確匹配;面狀實體則可依次計算質(zhì)心距離、面積重疊比排除候選集中大部分實體，最后計算Hausdorff距離完成匹配。

4結語

本文針對網(wǎng)格化河湖管理的數(shù)據(jù)，提出了一種基于四進制Morton碼的分層式地理實體編碼方案，并討論了面向河湖數(shù)據(jù)對象的逐層篩選式的地理實體匹配策略。通過地理實體編碼將其空間位置信息存儲在編碼字段中，檢索時將空間位置的檢索轉換為編碼之間的相似性匹配，提高了檢索效率，配合逐層篩選的地理實體匹配方式，為網(wǎng)格化河湖數(shù)據(jù)管理中快速定位、快速檢索與準確匹配提供了重要方法。

參考文獻

[1]李德仁，賓洪超，邵振峰.國土資源網(wǎng)格化管理與服務系統(tǒng)的設計與實現(xiàn)[J].武漢大學學報（信息科學版），2008（01）：1-6.

[2]李琦，羅志清，郝力，安真臻.基于不規(guī)則網(wǎng)格的城市管理網(wǎng)格體系與地理編碼[J].武漢大學學報（信息科學版），2005（05）：408-411.

[3]彭瑞，江瑞.關于地理實體編碼設計和應用的研究[J].現(xiàn)代測繪，2012，35（03）：23-26.

[4]張?zhí)祢裕瑖捞﹣恚鹾ｒ裕瑮钣纻b.基于Morton碼的土地空間網(wǎng)格數(shù)據(jù)組織與檢索[J].農(nóng)業(yè)工程學報，2013，29（S1）：235-243.

作者信息

蔡赟 1989-12，男，江蘇省揚州市，江蘇中誠土地房地產(chǎn)評估規(guī)劃咨詢有限公司，江蘇省揚州市邗江區(qū)文匯西路173號 ?現(xiàn)代廣場25幢6樓，225000，13338865952

呂景旭，1996-11，男，，山東省微山縣，地圖制圖學與地理信息工程，東南大學交通學院，南京市江寧區(qū)東南大學路2號，211189，15051879652