蔡赟 呂景旭
摘要 網(wǎng)格化管理由于其可以保證地理實體的完整性、管理的便捷性等優(yōu)勢,在河湖數(shù)據(jù)管理中得到廣泛的應(yīng)用。傳統(tǒng)編碼方案基于矩形或經(jīng)緯網(wǎng)的分幅方法,對地理實體位置信息的表達(dá)不適用于網(wǎng)格化管理。本文針對河湖數(shù)據(jù)網(wǎng)格化管理,在研究相關(guān)編碼方案的基礎(chǔ)上,基于四進(jìn)制Morton碼的編碼思想,對常規(guī)線性四叉樹存在的一些弊端進(jìn)行改進(jìn),設(shè)計了一種基于地理實體位置信息的編碼方案,所設(shè)計方案提高了空間利用率與查詢效率,便于河湖數(shù)據(jù)的維護與更新。
關(guān)鍵詞網(wǎng)格化;地理實體編碼;四叉樹;Morton碼
1引言
在地學(xué)領(lǐng)域中,網(wǎng)格化是一種依照道路、水系、行政區(qū)劃邊界等要素對地理空間進(jìn)行劃分的方法[1]。劃分形成的多邊形稱為網(wǎng)格單元,各個網(wǎng)格單元相互鄰接且不發(fā)生交叉,其間的空間關(guān)系是隱含表達(dá)的[2]。與傳統(tǒng)分幅方式相比,網(wǎng)格化可以最大限度地保證地理要素的完整性與連續(xù)性。在數(shù)據(jù)處理中,可減少接邊的工作量,提高工作效率,在實際應(yīng)用中方便日常管理,因此在河湖數(shù)據(jù)管理中得到了廣泛應(yīng)用。
2編碼方法
2.1四叉樹與Morton碼地址編碼
四叉樹是一種應(yīng)用十分廣泛的數(shù)據(jù)結(jié)構(gòu)[5],它的建立是將地理空間劃分為四個相等的子空間,然后通過遞歸的方式對子空間重復(fù)劃分直至滿足一定要求后停止,劃分后對應(yīng)的格網(wǎng)信息存儲在葉結(jié)點中,位置信息則隱含于結(jié)點編號(即地址編碼)中。Morton碼通過將二進(jìn)制的行號和列號交叉組合為格網(wǎng)賦予地址編碼。相比于其他編碼方案中直接記錄四叉樹行列號的方式[3],四進(jìn)制Morton碼將二維數(shù)據(jù)轉(zhuǎn)為一維數(shù)據(jù),同時將空間層次包含在編碼中,更有利于數(shù)據(jù)結(jié)構(gòu)的設(shè)計以及存儲。
當(dāng)?shù)乩韺嶓w位置分布較為均勻時,四叉樹各個分支之間較為平衡,數(shù)據(jù)插入和查詢都有較高的效率;而當(dāng)數(shù)據(jù)量較大且分布不均時,隨著數(shù)據(jù)的逐漸插入,不均衡的數(shù)據(jù)分布將導(dǎo)致四叉樹各分支之間失去平衡。由于存儲實體的結(jié)點均為葉結(jié)點,中間結(jié)點與根結(jié)點均不參與存儲,檢索時必須遍歷至葉結(jié)點才能結(jié)束,這樣就會增加檢索深度,降低檢索的效率,同時造成存儲空間的浪費。
因此,本文在建立四叉樹時,將地理實體信息存儲在完全包含該實體的最低層次結(jié)點中,而不是完全存儲在葉結(jié)點中。這樣改變存儲位置之后,根結(jié)點、中間結(jié)點就與葉結(jié)點一樣,需要使用四進(jìn)制Morton碼來獲取地址編碼。改進(jìn)前后的四叉樹以及Morton碼的應(yīng)用如圖1、表1所示(根結(jié)點代表第0層):
以實體C為例,該實體涉及第2層的結(jié)點00與結(jié)點02,但由于結(jié)點00、01、02、03為第一層的同一結(jié)點的子結(jié)點,故檢索區(qū)域包含2*2個結(jié)點,在使用單層Morton碼時,對應(yīng)的區(qū)域邊長值為2,在四叉樹中檢索至樹的第2層獲取到相關(guān)實體,需要用2個結(jié)點來存儲實體信息。而在使用分層Morton碼時,包含實體C的最小格網(wǎng)為以上四個結(jié)點的父結(jié)點,處于四叉樹中第1層,對應(yīng)的分層Morton碼為00,僅需1個結(jié)點存儲,檢索時遍歷至樹的第1層即可結(jié)束。由以上對比易知,改進(jìn)后的分層Morton碼以及四叉樹充分利用了現(xiàn)有結(jié)點,節(jié)約了存儲空間,同時降低了涉及范圍較廣的實體的檢索深度,提高了檢索效率。
2.2 格網(wǎng)劃分與編碼
格網(wǎng)的劃分與編碼設(shè)計基于2.1中分層Morton編碼的基本思想進(jìn)行。由于四進(jìn)制分層Morton碼的長度與所在層次相關(guān),為保證碼段長度恒定,當(dāng)碼段長度空缺時使用“9”進(jìn)行補位。如圖2,編碼由四部分組成,前三部分為不同層次的位置碼段,分別為行政區(qū)劃位置碼(5位)、網(wǎng)格單元位置碼(4位)、實體位置碼(7位),最后一部分為擴展碼(2位)。
第一部分為行政區(qū)劃位置碼,通過對根結(jié)點存儲的地理空間劃分2次,最終劃分為3層,第2層的結(jié)點共16個,政區(qū)實體存儲在四叉樹中0、1、2層,碼段長度為5位,其中Morton碼3位,順序碼2位(表示市級行政編號)。
第二部分為網(wǎng)格單元位置碼,在第一次劃分的基礎(chǔ)上對地理空間再劃分2次,空間總共被劃分為5層,網(wǎng)格單元主要存儲在四叉樹中3、4層,第4層的結(jié)點共256個,碼段長度為6位,其中Morton碼4位,順序碼2位(表示網(wǎng)格單元編號)。
第三部分為實體位置碼,在第二次劃分的基礎(chǔ)上再劃分4次,至此,空間總共被劃分為9層,地理實體主要存儲在四叉樹中5、6、7、8層,葉結(jié)點共65536個,碼段長度為11位,其中Morton碼8位,順序碼3位(地理實體編號,保證地理實體的唯一性)。
第四部分的擴展碼默認(rèn)為“00”,方便數(shù)據(jù)的存儲與管理。
同時,為避免編碼長度過長,數(shù)據(jù)表中將前兩個碼段與后兩個碼段分別存儲在兩個字段中。這樣,基于分層思想的編碼方式,將地理實體位置信息通過四進(jìn)制Morton碼將空間索引記錄在編碼中,為地理實體的快速檢索提供了依據(jù)。
3地理實體檢索與匹配
在網(wǎng)格化河湖管理系統(tǒng)中,根據(jù)編碼可實現(xiàn)未知地理實體與數(shù)據(jù)庫中地理實體的初步匹配。日常管理中,網(wǎng)格單元由專門的巡查人員進(jìn)行巡查,發(fā)現(xiàn)異常時將信息進(jìn)行上報。服務(wù)器端可根據(jù)巡查人員位置以及上報的實體信息自動生成地理實體位置相關(guān)碼段。依照生成的位置碼段,與數(shù)據(jù)庫中的實體進(jìn)行編碼匹配,最終將檢索范圍限制在包含該實體的最小四叉樹網(wǎng)格內(nèi)。圖3中(a)(b)分別為江蘇省和南京市的格網(wǎng)劃分與Morton編碼,表2為江蘇省部分市區(qū)的行政區(qū)劃位置碼:
如圖3(a)中所示,通過兩次劃分將江蘇省所處空間分為3層,各地級市根據(jù)其空間位置存儲在不同層次的結(jié)點中,如完全包含南京市的最小結(jié)點為第2層中Morton碼003的結(jié)點,依據(jù)其行政區(qū)劃代碼3201得到順序碼為01,最終得到南京的行政區(qū)劃位置碼為00301。同理可得,完全包含蘇州的最小結(jié)點為第1層中Morton碼01的結(jié)點,其行政區(qū)劃位置碼為01905;揚州處在第1次劃分的分割線上,只有根結(jié)點可完全包含該政區(qū)實體,因此其行政區(qū)劃位置碼為09910。圖中根據(jù)巡查人員所處A點位置信息,依照點與多邊形關(guān)系判斷出該巡查員位于南京市范圍內(nèi),因此自動生成行政區(qū)劃碼段為00301。確定行政區(qū)劃范圍之后,如圖3(b)所示,在003結(jié)點的基礎(chǔ)上通過同樣的方法繼續(xù)進(jìn)行格網(wǎng)劃分和位置關(guān)系判定,可以自動生成網(wǎng)格單元位置編碼為129914(位置關(guān)系判定得到所處網(wǎng)格單元順序碼為14)。在確定網(wǎng)格單元的基礎(chǔ)上,根據(jù)上報的地理實體位置信息,可知包含該實體的最小四叉樹結(jié)點位于四叉樹中第5層,Morton碼為21999,因此生成的實體編碼為21999999000(順序碼默認(rèn)為000)。至此便可獲得上報地理實體編碼為“003011299141299999900000”,進(jìn)而在數(shù)據(jù)庫中通過編碼匹配篩選出符合條件的實體進(jìn)行進(jìn)一步匹配。
通過編碼篩選之后只有很少的地理實體進(jìn)入候選集,可大大減少與待匹配的實體進(jìn)行精確匹配的時間。在河湖數(shù)據(jù)中,點狀實體多為水利設(shè)施,在空間分布上較為分散,可通過計算點實體間的曼哈頓距離完成匹配;線狀實體多為單線河、航道數(shù)據(jù)等,可依次通過計算長度偏差、首點終點連線的方向偏差進(jìn)一步縮小檢索范圍,最終通過計算Hausdorff距離實現(xiàn)精確匹配;面狀實體則可依次計算質(zhì)心距離、面積重疊比排除候選集中大部分實體,最后計算Hausdorff距離完成匹配。
4結(jié)語
本文針對網(wǎng)格化河湖管理的數(shù)據(jù),提出了一種基于四進(jìn)制Morton碼的分層式地理實體編碼方案,并討論了面向河湖數(shù)據(jù)對象的逐層篩選式的地理實體匹配策略。通過地理實體編碼將其空間位置信息存儲在編碼字段中,檢索時將空間位置的檢索轉(zhuǎn)換為編碼之間的相似性匹配,提高了檢索效率,配合逐層篩選的地理實體匹配方式,為網(wǎng)格化河湖數(shù)據(jù)管理中快速定位、快速檢索與準(zhǔn)確匹配提供了重要方法。
參考文獻(xiàn)
[1]李德仁,賓洪超,邵振峰.國土資源網(wǎng)格化管理與服務(wù)系統(tǒng)的設(shè)計與實現(xiàn)[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2008(01):1-6.
[2]李琦,羅志清,郝力,安真臻.基于不規(guī)則網(wǎng)格的城市管理網(wǎng)格體系與地理編碼[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2005(05):408-411.
[3]彭瑞,江瑞.關(guān)于地理實體編碼設(shè)計和應(yīng)用的研究[J].現(xiàn)代測繪,2012,35(03):23-26.
[4]張?zhí)祢?,?yán)泰來,王海蛟,楊永俠.基于Morton碼的土地空間網(wǎng)格數(shù)據(jù)組織與檢索[J].農(nóng)業(yè)工程學(xué)報,2013,29(S1):235-243.
作者信息
蔡赟 1989-12,男,江蘇省揚州市,江蘇中誠土地房地產(chǎn)評估規(guī)劃咨詢有限公司,江蘇省揚州市邗江區(qū)文匯西路173號 ?現(xiàn)代廣場25幢6樓,225000,13338865952
呂景旭,1996-11,男,,山東省微山縣,地圖制圖學(xué)與地理信息工程,東南大學(xué)交通學(xué)院,南京市江寧區(qū)東南大學(xué)路2號,211189,15051879652