蔡赟 呂景旭

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

關(guān)鍵詞網(wǎng)格化;地理實(shí)體編碼;四叉樹(shù);Morton碼

1引言

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

2編碼方法

2.1四叉樹(shù)與Morton碼地址編碼

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

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

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

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

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

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

第一部分為行政區(qū)劃位置碼，通過(guò)對(duì)根結(jié)點(diǎn)存儲(chǔ)的地理空間劃分2次，最終劃分為3層，第2層的結(jié)點(diǎn)共16個(gè)，政區(qū)實(shí)體存儲(chǔ)在四叉樹(shù)中0、1、2層，碼段長(zhǎng)度為5位，其中Morton碼3位，順序碼2位（表示市級(jí)行政編號(hào)）。

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

第三部分為實(shí)體位置碼，在第二次劃分的基礎(chǔ)上再劃分4次，至此，空間總共被劃分為9層，地理實(shí)體主要存儲(chǔ)在四叉樹(shù)中5、6、7、8層，葉結(jié)點(diǎn)共65536個(gè)，碼段長(zhǎng)度為11位，其中Morton碼8位，順序碼3位（地理實(shí)體編號(hào)，保證地理實(shí)體的唯一性）。

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

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

3地理實(shí)體檢索與匹配

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

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

[3]彭瑞，江瑞.關(guān)于地理實(shí)體編碼設(shè)計(jì)和應(yīng)用的研究[J].現(xiàn)代測(cè)繪，2012，35（03）：23-26.

[4]張?zhí)祢裕瑖?yán)泰來(lái)，王海蛟，楊永俠.基于Morton碼的土地空間網(wǎng)格數(shù)據(jù)組織與檢索[J].農(nóng)業(yè)工程學(xué)報(bào)，2013，29（S1）：235-243.

作者信息

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

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