汪紅松 周曉光

摘? ?要：地表覆蓋/土地利用矢量數(shù)據(jù)中存在大量包含成千上萬個(gè)空洞（甚至嵌套空洞）的復(fù)雜多邊形，現(xiàn)有空間數(shù)據(jù)索引沒有表達(dá)復(fù)雜多邊形及其空洞之間的包含關(guān)系，導(dǎo)致空間數(shù)據(jù)沖突檢測(cè)與更新等處理存在計(jì)算量大、效率低等問題. 針對(duì)此問題，提出了一種存儲(chǔ)多邊形包含關(guān)系的四叉樹索引方法. 該方法根據(jù)結(jié)點(diǎn)中的多邊形與四叉樹相應(yīng)象限中軸線相交的方式將多邊形對(duì)象分為5種類型，即僅與X正軸相交、僅與X負(fù)軸相交、僅與Y正軸相交、僅與Y負(fù)軸相交以及與XY軸都相交，并將這些多邊形對(duì)象分別存儲(chǔ)在相應(yīng)層次索引結(jié)點(diǎn)中的5個(gè)子列表（桶）中，然后在結(jié)點(diǎn)多邊形對(duì)象中存儲(chǔ)多邊形之間的父子包含關(guān)系. 最后設(shè)計(jì)并實(shí)現(xiàn)了該索引及相應(yīng)的查詢、插入、刪除等算法，并用實(shí)際地表覆蓋數(shù)據(jù)驗(yàn)證了本文方法的有效性. 實(shí)驗(yàn)結(jié)果表明，采用本文索引方法的復(fù)雜地表覆蓋矢量數(shù)據(jù)增量更新效率數(shù)倍于現(xiàn)有四叉樹索引方法，且隨著數(shù)據(jù)量的增加效率提高更明顯.

關(guān)鍵詞：空間索引;復(fù)雜多邊形;包含關(guān)系;四叉樹;空間數(shù)據(jù)管理

中圖分類號(hào)：P208? ?? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)志碼：A

Abstract：There are a large number of complex polygons containing thousands of holes （or even nested holes） in the land cover/land use vector data， and the existing spatial data indexing method has failed to indicate the inclusion relationship between complex polygons and their holes， resulting in computationally heavy and inefficient processing such as spatial data conflict detection and updating. In order to solve this problem， an improved quadtree spatial index method with inclusion relations of the complex polygons is presented in this paper. The method classifies the polygons in the nodes into five types according to the way they intersect the axes in the corresponding quadrant of the quadtree， i.e.， intersect only the X positive axis， intersect only the X negative axis， intersect only the Y positive axis， intersect only the Y negative axis， and intersect both X and Y axes， and stores each of these polygons in five sublists （buckets） in the corresponding hierarchical index nodes， and then stores the parent-child inclusion relationship between the polygons in the node polygon objects. The authors developed the spatial index structure with inclusion relations and the algorithms of the corresponding operations（e.g.，insert， delete and query）for the complex polygons. The effectiveness of the approach in this paper is verified by an experiment of land cover data incremental updating， experimental results show that the time efficiency of the incremental updating is increased about several times using the proposed index method than that of the traditional quadtree index， and the improvement in efficiency is more significant with increasing data volume.

Key words：spatial index;complex polygon;inclusion relation;quadtrees;spatial data management

隨著全球30 m地表覆蓋地圖GlobeLand30[1-2]和全球10 m地表覆蓋數(shù)據(jù)FROM-GLC10[3]的完成與發(fā)布，全球地表覆蓋數(shù)據(jù)已成為聯(lián)合國(guó)等國(guó)際組織開展全球變化與可持續(xù)發(fā)展等重大科學(xué)研究的基礎(chǔ)數(shù)據(jù). 全球地表覆蓋數(shù)據(jù)的驗(yàn)證、服務(wù)與持續(xù)更新成為本領(lǐng)域的研究熱點(diǎn)[4-8].在全球地表覆蓋矢量數(shù)據(jù)更新方面，周曉光等[7]提出了一種基于二維交細(xì)分拓?fù)潢P(guān)系的地表覆蓋/土地利用數(shù)據(jù)增量更新方法，但由于地表覆蓋矢量數(shù)據(jù)中存在大量包含成千上萬個(gè)空洞（甚至嵌套空洞）的復(fù)雜多邊形，目前空間數(shù)據(jù)模型中沒有表達(dá)復(fù)雜多邊形及其空洞之間的包含關(guān)系，導(dǎo)致在計(jì)算增量多邊形與已存在的復(fù)雜多邊形間二維交時(shí)存在計(jì)算量大、效率低等問題.

GIS中空間數(shù)據(jù)處理一般包括過濾和精化計(jì)算兩個(gè)步驟，空間數(shù)據(jù)索引用來過濾掉大部分無關(guān)的目標(biāo)，使得精化計(jì)算僅在少數(shù)密切相關(guān)目標(biāo)間進(jìn)行的效率提升的特殊空間數(shù)據(jù)結(jié)構(gòu). 目前，空間數(shù)

據(jù)索引方法包括傳統(tǒng)矢量數(shù)據(jù)索引的四叉樹[9-10]、

R樹[11-12]、R+樹[13]、R*樹[14-15]、網(wǎng)格索引[16]、Hilbert R樹[17]等和軌跡數(shù)據(jù)索引Geohash-Trees[18]等. 上述傳統(tǒng)矢量數(shù)據(jù)索引方法均采用目標(biāo)的最小外接矩形（MBR）減小索引結(jié)構(gòu)的存儲(chǔ)量并提高過濾效率. 但是對(duì)于復(fù)雜多邊形，現(xiàn)有索引方法僅存儲(chǔ)了其外邊界的MBR，不能表達(dá)復(fù)雜多邊形及其空洞間的包含關(guān)系，在空間數(shù)據(jù)沖突檢測(cè)與更新處理中，無關(guān)空洞不能通過索引而過濾掉，大量空洞需參與精化計(jì)算，是導(dǎo)致計(jì)算量大、效率低等問題的根本原因.

圖1所示為地表覆蓋矢量數(shù)據(jù)的局部示例，圖中C為一個(gè)包含上千個(gè)空洞的復(fù)雜多邊形，圖1（a）中B、 D、 E、 F等都是其空洞，其中陰影部分為其他圖層圖斑，在當(dāng)前圖層中為空白區(qū)域. P1為增量多邊形（圖1（b）），P1只與C和它的一個(gè)空洞多邊形B和空白區(qū)域存在二維交，需要進(jìn)行更新處理. 但采用現(xiàn)有索引方法，需要計(jì)算P1與C及其所有空洞多邊形的拓?fù)潢P(guān)系，導(dǎo)致更新處理效率極低. 如果在索引結(jié)構(gòu)中能夠存儲(chǔ)復(fù)雜多邊形與其空洞間的包含關(guān)系，無關(guān)的空洞通過索引過濾掉，那么地表覆蓋數(shù)據(jù)更新效率有望大大提高. 根據(jù)上述分析，本文提出一種存儲(chǔ)復(fù)雜多邊形包含關(guān)系的空間數(shù)據(jù)索引方法.

地表覆蓋矢量數(shù)據(jù)嵌套復(fù)雜，多邊形MBR重疊嚴(yán)重，若構(gòu)建索引R樹結(jié)構(gòu)，則索引性能不佳[15]，同時(shí)R樹索引無法避免地重復(fù)存儲(chǔ)空間對(duì)象，造成空間數(shù)據(jù)更新時(shí)存儲(chǔ)的包含關(guān)系一致性維護(hù)困難. 處理面目標(biāo)的四叉樹結(jié)構(gòu)主要有線性四叉樹、PMR四叉樹、CIF四叉樹等結(jié)構(gòu)[9，19-20]. 線性四叉樹用自定義大小的網(wǎng)格映射空間目標(biāo)[21]，由于地表覆蓋矢量數(shù)據(jù)面積分布極度不均，難以選擇大小合適的網(wǎng)格，同時(shí)索引中空間對(duì)象也無法避免重復(fù)存儲(chǔ);PMR四叉樹索引以線段而非以面目標(biāo)作為整體概念;CIF四叉樹索引以分層的網(wǎng)格映射空間目標(biāo)[22]，索引結(jié)構(gòu)形態(tài)不依賴空間對(duì)象插入的順序，不重復(fù)存儲(chǔ)空間對(duì)象，同時(shí)空間數(shù)據(jù)更新時(shí)，結(jié)點(diǎn)變更較小[21-23]，本文在CIF四叉樹基礎(chǔ)上提出一種存儲(chǔ)拓?fù)浒P(guān)系的四叉樹空間索引方法.

1? ?包含關(guān)系四叉樹索引的建立

1.1? ?多邊形包含關(guān)系的表達(dá)

復(fù)雜多邊形與其空洞多邊形之間的嵌套包含關(guān)系類似于父子關(guān)系，可通過父-子-孫間的序關(guān)系來表達(dá)多邊形之間嵌套包含關(guān)系，如圖2所示.

圖2中H的父多邊形為F，F(xiàn)與H互為父多邊形與子多邊形，H與C不存在直接包含關(guān)系（H為C的孫子多邊形）. 子多邊形被包圍在父多邊形的相應(yīng)內(nèi)環(huán)（Ring in Parent，RIP）中，多邊形F包含在C中的內(nèi)環(huán)rc1中（即F的RIP為rc1），因此，內(nèi)環(huán)是父多邊形和子多邊形之間的聯(lián)系，內(nèi)環(huán)嵌套體現(xiàn)多邊形之間復(fù)雜包含關(guān)系. 一個(gè)多邊形的內(nèi)環(huán)可以被多個(gè)子多邊形共享，F(xiàn)的內(nèi)環(huán)rf2包含了T、J、I共 3個(gè)子多邊形. 內(nèi)環(huán)不是一個(gè)獨(dú)立對(duì)象，因此不能直接建立內(nèi)環(huán)對(duì)象與其所包圍的子多邊形對(duì)象的對(duì)應(yīng)關(guān)系，但通過遍歷內(nèi)環(huán)所在多邊形的子多邊形，判斷具有共同RIP的子多邊形即可確定上述對(duì)應(yīng)關(guān)系. 因此，一個(gè)多邊形的直接包含關(guān)系可表達(dá)為：{父多邊形，在父多邊形中相應(yīng)的環(huán)，包含的子多邊形}.

根據(jù)以上分析，設(shè)CP（Current Polygon）表示當(dāng)前多邊形，PP（Parent Polygon）為CP的父多邊形，RIPID（Ring in Parent ID）為CP在PP中相應(yīng)的內(nèi)環(huán)序號(hào)，CPL（Children Polygon List ）為CP的子多邊形指針數(shù)組，為每個(gè)內(nèi)環(huán)建立子多邊形列表，則四叉樹結(jié)點(diǎn)中多邊形對(duì)象的數(shù)據(jù)結(jié)構(gòu)可表達(dá)為：{CP，PP，RIPID，CPL}.

空間數(shù)據(jù)往往分圖層構(gòu)建，且具有鋪蓋特征，其中復(fù)雜多邊形與其空洞多邊形可能分別存儲(chǔ)在不同圖層中，導(dǎo)致一個(gè)圖層中存在很多空白區(qū)域，如圖1中的陰影部分（下同）. 當(dāng)前圖層只存儲(chǔ)了空白區(qū)域的RIP，而無相應(yīng)多邊形對(duì)象. 由于空白區(qū)域的RIP不能獨(dú)立存儲(chǔ)為多邊形對(duì)象，為完整表達(dá)該RIP相關(guān)的包含關(guān)系，本文引入內(nèi)環(huán)虛擬多邊形對(duì)象來填滿復(fù)雜多邊形內(nèi)連續(xù)的空白區(qū)域，即內(nèi)環(huán)虛擬多邊形對(duì)象為一個(gè)復(fù)雜多邊形內(nèi)空洞邊界構(gòu)建的虛擬對(duì)象，其結(jié)構(gòu)為{CP，PP，-RIPID，?}. 其中CP為內(nèi)環(huán)虛擬多邊形，PP為內(nèi)環(huán)虛擬多邊形的父多邊形，-RIPID為該內(nèi)環(huán)在PP中的序號(hào)（用負(fù)號(hào)來區(qū)別于實(shí)際存在的多邊形）.

為確定多邊形間的包含關(guān)系，建立了如下4條判別規(guī)則. 設(shè)多邊形P1、P2，若滿足以下規(guī)則，則P1直接包含P2.

規(guī)則1? ?P1有內(nèi)環(huán);

規(guī)則2? ?P2的MBR被P1的MBR包含，同時(shí)與P1的某一內(nèi)環(huán)r的MBR相等（如圖2中F與rc1）或相交（如圖2中T與rf2）;

規(guī)則3? ?P2上任取一頂點(diǎn)在r的環(huán)內(nèi)或環(huán)上;

規(guī)則4? ?不存在MBR小于P1的多邊形包含P2.

上述規(guī)則，每條都是建立在前一條規(guī)則的基礎(chǔ)上. 其中規(guī)則2需要遍歷P1的內(nèi)環(huán)，對(duì)滿足規(guī)則2的內(nèi)環(huán)，再使用規(guī)則3判別. 若P2的子多邊形均為簡(jiǎn)單多邊形，則前3條規(guī)則可確定P1與P2的包含關(guān)系，否則利用規(guī)則4進(jìn)一步約束，以排除嵌套的間接包含關(guān)系. 規(guī)則1判別多邊形是否有內(nèi)環(huán)的時(shí)間復(fù)雜度為常量O（1），若P1所有內(nèi)環(huán)數(shù)的總邊數(shù)為e，則規(guī)則2遍歷P1的內(nèi)環(huán)并判別MBR是否相交的主要開銷為遍歷P1內(nèi)環(huán)計(jì)算MBR，其時(shí)間復(fù)雜度為

O（e），若P2的RIP邊數(shù)為a，則規(guī)則3、4判別的時(shí)間開銷為判斷點(diǎn)是否在多邊形內(nèi)，其復(fù)雜度為O（a）[24]. 因此，判別P1包含P2的時(shí)間復(fù)雜度為O（e+a）.

1.2? ?對(duì)現(xiàn)有四叉樹的改進(jìn)

CIF四叉樹將數(shù)據(jù)空間遞歸地劃分，直至產(chǎn)生的子象限包含的對(duì)象數(shù)不大于設(shè)定的閾值，在分解過程中，所有與象限中軸線相交的對(duì)象只與該象限對(duì)應(yīng)的結(jié)點(diǎn)相關(guān)聯(lián)，屬于一個(gè)結(jié)點(diǎn)的矩形不屬于任何祖先結(jié)點(diǎn)[22]. 索引空間查詢過程分為3個(gè)階段[21]，先經(jīng)過兩次篩選，然后精確匹配. CIF四叉樹索引查詢的第一次篩選判別與查詢條件（查詢窗口、查詢點(diǎn)）相交的四叉樹結(jié)點(diǎn)，確定候選多邊形集，第二次篩選依據(jù)候選多邊形MBR與查詢條件是否相交，以縮小結(jié)果集的范圍，最后通過精確計(jì)算判斷二者是否相交，確定查詢結(jié)果集. Wei 等[10]提出存儲(chǔ)結(jié)點(diǎn)中所有多邊形MBR并作為范圍MBR，以加速篩選第二階段的候選目標(biāo)，但效果并不理想. 第二次篩選過程中，若四叉樹結(jié)點(diǎn)范圍與查詢條件相交，仍需要遍歷該結(jié)點(diǎn)中所有多邊形對(duì)象. 實(shí)際上在四叉樹離根近的上層結(jié)點(diǎn)中，結(jié)點(diǎn)范圍大，相應(yīng)象限的中軸線長(zhǎng)，與其相交的多邊形數(shù)量也很多.

圖3所示為根結(jié)點(diǎn)中存儲(chǔ)的多邊形示例，刪除與XY軸均相交的的復(fù)雜多邊形后可見與中軸線相交的眾多小圖斑（圖3（b））. 在索引查詢時(shí)，當(dāng)查詢窗口僅與X負(fù)軸相交，則仍需要遍歷根結(jié)點(diǎn)中所有多邊形，以篩選出目標(biāo)多邊形，盡管大多數(shù)多邊形與查詢窗口相距較遠(yuǎn).

為提高第二次篩選的效率，設(shè)四叉樹結(jié)點(diǎn)對(duì)應(yīng)象限的中軸線交點(diǎn)為坐標(biāo)原點(diǎn)，將結(jié)點(diǎn)中的多邊形按照其與象限中軸線相交的方式不同，分為只與X正軸相交、只與X負(fù)軸相交、只與Y正軸相交、只與Y負(fù)軸相交以及與XY軸都相交5種類型（如圖4所示），并設(shè)計(jì)了5個(gè)桶（多邊形列表）來存儲(chǔ)相應(yīng)多邊形. 篩選時(shí)根據(jù)桶MBR與查詢條件的相交情況確定是否遍歷桶內(nèi)多邊形. 同時(shí)，將與X軸相交、XY軸均相交的桶內(nèi)多邊形根據(jù)其MBR最小X坐標(biāo)升序排序，與Y軸相交的桶內(nèi)多邊形根據(jù)其MBR最小Y坐標(biāo)升序排序，使得索引查詢時(shí)能在有序序列中篩選可能的查詢目標(biāo).

根據(jù)上述分析，四叉樹索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可表達(dá)為：{NID，NMBR，Subtrees，Depth，PPtr，XYL，XpL，XnL，YpL，YnL}. 其中，NID為結(jié)點(diǎn)的ID，NMBR為結(jié)點(diǎn)的范圍MBR，Subtrees為子樹（四叉），Depth為結(jié)點(diǎn)層次，PPtr為父結(jié)點(diǎn)指針，XYL、XpL、XnL、YpL、YnL分別為多邊形與中軸線5種不同相交方式對(duì)應(yīng)桶. 結(jié)點(diǎn)中設(shè)計(jì)指向父結(jié)點(diǎn)的指針是為了方便四叉樹中自下而上的遍歷.

建立四叉樹索引的基本步驟為：

1）根據(jù)空間數(shù)據(jù)范圍確定根結(jié)點(diǎn)MBR并建立

根結(jié)點(diǎn)，將與根結(jié)點(diǎn)中軸線相交的多邊形對(duì)象按照與中軸線相交的類型有序地插入到相應(yīng)桶內(nèi);

2）根據(jù)中軸線將結(jié)點(diǎn)等分為4個(gè)子象限并建立相應(yīng)子樹，將MBR完全包含在子象限范圍的多邊形存儲(chǔ)在子樹中，并設(shè)置子樹指向父結(jié)點(diǎn)的線索指針PPtr;

3）對(duì)4個(gè)子樹遞歸地重復(fù)步驟2，直到子樹中多邊形數(shù)量達(dá)到結(jié)點(diǎn)分裂閾值，獲得無包含關(guān)系的四叉樹索引;

4）對(duì)每個(gè)多邊形對(duì)象利用PPtr向根搜索并判別父多邊形，同時(shí)將該多邊形加入到父多邊形相應(yīng)內(nèi)環(huán)的CPL指針數(shù)組中;

5）掃描CPL，依據(jù)內(nèi)環(huán)與子多邊形的對(duì)應(yīng)關(guān)系，判別并插入虛擬多邊形對(duì)象.

根據(jù)上述建立索引方法對(duì)圖1（a）地表覆蓋示例數(shù)據(jù)建立四叉樹索引，并以多邊形對(duì)象C、F、T為例表達(dá)它們的包含關(guān)系，結(jié)果如圖5所示（設(shè)分裂閾值Tnum = 2）. 圖5（a）中rc1、rc2、rc3、rf1、rf2及rq1分別為多邊形C、F及Q的內(nèi)環(huán)，其中內(nèi)環(huán)rc2和rq1是其他圖層數(shù)據(jù)，環(huán)內(nèi)空間未鋪滿，因此建立相應(yīng)的內(nèi)環(huán)虛擬多邊形對(duì)象vp1和vp2. 雖然x區(qū)域?yàn)槠渌麍D層數(shù)據(jù)，但是沒有包含在任何多邊形內(nèi)，無需建立內(nèi)環(huán)虛擬多邊形對(duì)象. 索引根結(jié)點(diǎn)各桶存儲(chǔ)情況為：XYL桶中存儲(chǔ)多邊形C、F、vp1、B;XnL桶中存儲(chǔ)S;XpL桶為空;YnL桶為空;YpL桶中存儲(chǔ)H、G;圖5（b）中多邊形F的父多邊形指針指向多邊形C，F(xiàn)存在于C中內(nèi)環(huán)對(duì)應(yīng)的子多邊形列表中，同時(shí)F又是多邊形T的父多邊形. 通過F可訪問父多邊形C及F在C中的內(nèi)環(huán)rc1，也可訪問子多邊形T及T在F中的內(nèi)環(huán)rf2 . 圖5（b）中子多邊形列表數(shù)組與多邊形的內(nèi)環(huán)相對(duì)應(yīng)，若多邊形無內(nèi)環(huán)（如多邊形T），則該數(shù)組為空，否則每個(gè)內(nèi)環(huán)對(duì)應(yīng)一個(gè)數(shù)組元素（子多邊形列表）. 因此，通過索引可直接獲取一個(gè)多邊形的父多邊形、其在父多邊形中相應(yīng)的內(nèi)環(huán)以及該多邊形直接包含的子多邊形.

建立存儲(chǔ)包含關(guān)系的四叉樹索引的時(shí)間開銷主要包括兩部分，即建立無包含關(guān)系的索引和確定索引樹中多邊形對(duì)象包含關(guān)系. 設(shè)多邊形數(shù)為n，索引結(jié)點(diǎn)數(shù)為N（樹深度為logN），則建立四叉樹索引的時(shí)間復(fù)雜度為O（n·logN）[19]. 搜索一個(gè)多邊形的父多邊形時(shí)，需要在向根的路徑上搜索MBR與該多邊形MBR相交的多邊形并遍歷它的內(nèi)環(huán). 設(shè)四叉樹結(jié)點(diǎn)中平均多邊形數(shù)為n/N，最壞情況下，向根搜索需遍歷的多邊形數(shù)為logN·n/N，故建立四叉樹索引并確定多邊形包含關(guān)系的時(shí)間總開銷為O（n·logN·n/N）（忽略包括建立無包含關(guān)系索引的時(shí)間及多邊形排序時(shí)間等低階項(xiàng)）. 可以看出，確定多邊形包含關(guān)系為本文索引建立的主要時(shí)間開銷，但索引是一次建立并存儲(chǔ)后永久使用，因此索引建立的代價(jià)相對(duì)于密集更新業(yè)務(wù)來說是可接受的.

2? ?存儲(chǔ)包含關(guān)系四叉樹索引操作

2.1? ?索引查詢

索引查詢操作是根據(jù)查詢條件，查詢與查詢點(diǎn)或區(qū)域相交的多邊形（集），查詢操作結(jié)果不包括內(nèi)環(huán)虛擬多邊形對(duì)象. 點(diǎn)查詢算法的主要步驟為：

1）自根向下搜索四叉樹結(jié)點(diǎn)中各桶的MBR是

否包含該查詢點(diǎn)，若包含，則進(jìn)一步判斷桶內(nèi)多邊形MBR是否包含查詢點(diǎn)，構(gòu)造候選多邊形集;

2）遍歷候選集查找第一個(gè)滿足查詢點(diǎn)在外環(huán)內(nèi)的多邊形P;

3）遍歷候選集中是否存在P的子多邊形且滿足查詢點(diǎn)在該子多邊形環(huán)外內(nèi)，則該子多邊形為新的P;

4）重復(fù)步驟3，直至P無子多邊形，則P為查詢結(jié)果;若P為虛擬多邊形，則返回空值.

區(qū)域查詢算法主要步驟為：

1）用與點(diǎn)查詢相似方法構(gòu)造候選多邊形集合;

2）遍歷候選多邊形，將外環(huán)與查詢窗口相交的多邊形（內(nèi)環(huán)虛擬多邊形除外）加入查詢結(jié)果集;

3）遍歷候選多邊形，若其在候選集中的子多邊形（或內(nèi)環(huán)虛擬多邊形）的RIP與查詢窗口相交則將其加入查詢結(jié)果集;

4）其他候選多邊形若窗口任意一點(diǎn)在其外環(huán)內(nèi)且不在其候選集中的子多邊形（或內(nèi)環(huán)虛擬多邊形）RIP內(nèi)，則加入到查詢結(jié)果集.

查詢算法一方面通過桶MBR的篩選，能合理避免不必要的索引搜索開銷，另一方面通過存儲(chǔ)的多邊形間父子包含關(guān)系，避免對(duì)候選集中多邊形外環(huán)及內(nèi)環(huán)逐一判別點(diǎn)在環(huán)內(nèi)的算法開銷.

2.2? ?索引中刪除多邊形對(duì)象

地表覆蓋矢量數(shù)據(jù)的增量更新中，地塊圖斑的新增、滅失、分解、合并等各種變更，可以理解為原有地塊的消失（刪除）和新地塊的出現(xiàn)（插入）[25]. 一個(gè)增量多邊形更新基態(tài)數(shù)據(jù)的過程大致為：在索引中搜索與增量多邊形相交的多邊形集合，逐一更新空間數(shù)據(jù)，從索引中刪除更新前的基態(tài)多邊形，向索引中插入更新產(chǎn)生的多邊形，并在更新過程中維護(hù)包含關(guān)系.

從四叉樹中刪除多邊形包括兩個(gè)任務(wù)：1）刪除該多邊形的子多邊形和父多邊形的包含關(guān)系;2）刪除該多邊形對(duì)象，若該多邊形有父多邊形，則建立父多邊形的內(nèi)環(huán)虛擬多邊形對(duì)象并插入到索引中.

從索引中刪除多邊形（設(shè)該多邊形為g）的算法主要步驟為：

1）從四叉樹索引中查詢多邊形g的位置;

2）從g的父多邊形對(duì)象的子多邊形列表中刪除g，從g的子多邊形對(duì)象中刪除父多邊形;

3）從當(dāng)前結(jié)點(diǎn)中刪除g，若父結(jié)點(diǎn)不為空，則以RIP構(gòu)建虛擬多邊形對(duì)象并插入索引;

4）若g所在結(jié)點(diǎn)為葉結(jié)點(diǎn)，則向上遞歸進(jìn)行結(jié)點(diǎn)合并操作.

上述算法中的步驟2）確保包含關(guān)系的一致性，即解除被刪除多邊形與其他多邊形的父子關(guān)系. 結(jié)點(diǎn)合并操作需要判斷g的父結(jié)點(diǎn)及g的兄弟結(jié)點(diǎn)中所有多邊形數(shù)量和是否低于結(jié)點(diǎn)分裂閾值Tnum，若低于Tnum則將這些多邊形并入父結(jié)點(diǎn)相應(yīng)桶中，并將父結(jié)點(diǎn)設(shè)置為葉結(jié)點(diǎn). 圖1（a）中刪除多邊形I、T、J的事件，如圖6（a）（c）所示，設(shè)Tnum=2，當(dāng)多邊形I從索引中刪除后，I有父多邊形，且刪除I后其RIP所圍區(qū)域未鋪滿，需根據(jù)其RIP建立虛擬多邊形對(duì)象rp3并插入索引（如圖6（b）所示）. 當(dāng)多邊形T、J刪除后，無需再建立虛擬多邊形對(duì)象，合并空的葉結(jié)點(diǎn)，索引更新后的結(jié)果如圖6（d）所示.

利用索引進(jìn)行增量數(shù)據(jù)更新時(shí)，待刪除多邊形位置已知，步驟2刪除該多邊形的包含關(guān)系，即修改其父多邊形和子多邊形對(duì)象的相應(yīng)屬性，步驟3依據(jù)被刪除多邊形RIP相應(yīng)子多邊形判別是否建立虛擬多邊形對(duì)象，步驟4合并結(jié)點(diǎn)是將不多于Tnum個(gè)多邊形移入父多結(jié)點(diǎn)中，以上步驟均可在常數(shù)時(shí)間內(nèi)完成，故時(shí)間復(fù)雜度為O（1），與現(xiàn)有四叉樹索引中刪除多邊形相比，時(shí)間開銷增加并不明顯.

2.3? ?索引中插入多邊形對(duì)象

插入多邊形對(duì)象前需先在索引中查詢插入位置，然后將該對(duì)象插入到索引中，并維護(hù)相關(guān)多邊形的包含關(guān)系. 插入多邊形（設(shè)該多邊形為g）的算法主要步驟為：

1）建立多邊形g的包含關(guān)系;

2）在四叉樹索引中查詢應(yīng)插入的結(jié)點(diǎn)，并將多邊形g插入到相應(yīng)的桶中;

3）若g內(nèi)有更新產(chǎn)生的內(nèi)環(huán)，則判別是否需要從索引中刪除相關(guān)的虛擬多邊形對(duì)象;

4）若插入的結(jié)點(diǎn)為葉結(jié)點(diǎn)，則判斷并處理插入操作可能引起的結(jié)點(diǎn)分裂.

圖7（a）顯示圖6（c）中用增量多邊形P1更新基態(tài)的結(jié)果. 增量多邊形P1與基態(tài)多邊形B、C及內(nèi)環(huán)虛擬多邊形vp1相交，與B交于外環(huán)，與C交于rc2和B的RIP兩個(gè)內(nèi)環(huán). 裁剪C（只裁剪相交的環(huán)）得C1及新內(nèi)環(huán)rc4，C1繼承C所有未參與裁剪的內(nèi)環(huán)及子多邊形，裁剪B得B1、B2，B1繼承B未參與裁剪的內(nèi)環(huán)及子多邊形. 通過面積屬性知內(nèi)環(huán)rc4未鋪滿子多邊形，建立內(nèi)環(huán)虛擬多邊形vp4. 最后從索引中刪除多邊形C、B、vp1，將多邊形對(duì)象C1、B1、B2、P1及vp4插入到索引中，如圖7（b）所示，其中索引根結(jié)點(diǎn)各桶存儲(chǔ)情況為：XYL桶存儲(chǔ)多邊形C1、F以及vp4;XnL桶存儲(chǔ)S;XpL桶存儲(chǔ)P1和B1;YnL桶存儲(chǔ)B2;YpL桶存儲(chǔ)H和G.

增量更新時(shí)需向索引中插入更新后產(chǎn)生的新多邊形以及增量多邊形. 設(shè)與增量多邊形相交的多邊形集合為S，S更新后的集合為S′，S′與S中多邊形的父多邊形集合的并為S+，由于增量多邊形的局部性，S、S′及S+中的多邊形數(shù)量遠(yuǎn)小于復(fù)雜多邊形內(nèi)環(huán)數(shù). 若在更新過程中一個(gè)多邊形的父多邊形未被更新時(shí)，則更新后的多邊形仍被其父多邊形直接包含或間接包含，因此，插入到索引中的多邊形對(duì)象應(yīng)在S+中搜索父多邊形并在索引中更新包含關(guān)系，其RIP為父多邊形中與更新操作相關(guān)的內(nèi)環(huán)（如B1、B2的RIP為C1的內(nèi)環(huán)vp4）. 所以增量更新過程中向索引插入多邊形時(shí)維護(hù)包含關(guān)系的時(shí)間開銷來自于構(gòu)建及搜索集合S+（RIP在增量更新時(shí)已確定），由于S+中多邊形數(shù)量很少，因此在已知RIP時(shí)，確定插入的多邊形的包含關(guān)系可在常數(shù)時(shí)間內(nèi)完成. 若插入的多邊形對(duì)象的RIP已經(jīng)被鋪滿，則應(yīng)刪除該內(nèi)環(huán)的虛擬多邊形對(duì)象. 對(duì)RIP內(nèi)的多邊形面積屬性求和并判斷其是否與RIP所圍面積相等，確定是否需要?jiǎng)h除虛擬多邊形，因此其時(shí)間復(fù)雜度為O（b），其中b為RIP的邊數(shù). 由插入多邊形對(duì)象引起的結(jié)點(diǎn)分裂的時(shí)間復(fù)雜度為O（Tnum），其中Tnum為分裂閾值常量. 在索引中查詢多邊形插入位置的時(shí)間開銷為遍歷從根向葉子的一條路徑并按順序插入多邊形，這與現(xiàn)有四叉樹插入時(shí)間一致，時(shí)間復(fù)雜度為O（n/N·logN），其中n/N為結(jié)點(diǎn)平均多邊形數(shù). 故索引中插入多邊形的時(shí)間復(fù)雜度為O（n/N·logN + b）. 與現(xiàn)有四叉樹索引相比，本文索引插入多邊形時(shí)間開銷增加了包含關(guān)系維護(hù)的時(shí)間.

3? ?實(shí)驗(yàn)與比較

為驗(yàn)證本文存儲(chǔ)包含關(guān)系四叉樹索引的有效性，以地表覆蓋矢量數(shù)據(jù)增量更新為例進(jìn)行了實(shí)驗(yàn)驗(yàn)證. 實(shí)驗(yàn)數(shù)據(jù)來源于30 m全球地表覆蓋數(shù)據(jù)（GlobeLand30），選取陜西省2000年和2009年兩景軌道號(hào)為127034的Landsat ETM+/TM 30 m分辨率遙感影像數(shù)據(jù). 影像覆蓋范圍為北緯32.432°～32.760°，東經(jīng)108.384°～109.100°，面積為2 373.1 km2. 用比值法、NDVI差值法、PCA差異法求得的結(jié)果影像作為初始變化信息并對(duì)其分類，為提高分類精度，采用2009年樣本數(shù)據(jù)對(duì)2009年影像進(jìn)行分類，然后以2009年數(shù)據(jù)為基態(tài)數(shù)據(jù)與2000年影像進(jìn)行變化信息提取，獲得增量數(shù)據(jù). 采用項(xiàng)目組開發(fā)的分類后遙感影像自動(dòng)矢量化與偽變化剔除組件自動(dòng)矢量化并剔除偽變化，生成原始基態(tài)矢量數(shù)據(jù)和增量矢量數(shù)據(jù)如圖8所示. 圖8（b）中方框內(nèi)為圖1所在區(qū)域. 該矢量數(shù)據(jù)采用地表覆蓋數(shù)據(jù)常用的Shapefile格式存儲(chǔ)[7]，多邊形總數(shù)為104 230個(gè)，數(shù)據(jù)中存在包含大量空洞的復(fù)雜多邊形，其中超過1 000個(gè)空洞的復(fù)雜多邊形6個(gè)，最復(fù)雜的多邊形包含5 573個(gè)空洞. 增量矢量數(shù)據(jù)為簡(jiǎn)單即不包含空洞的多邊形. 為實(shí)驗(yàn)需要，對(duì)獲取的矢量基態(tài)數(shù)據(jù)分別以不同最小面積剔除合并，得到不同多邊形數(shù)量的矢量基態(tài)數(shù)據(jù). 實(shí)驗(yàn)硬件環(huán)境為聯(lián)想楊天A8000微型計(jì)算機(jī)，CPU為i7-7700，內(nèi)存16 GB.

表1中基態(tài)多邊形“最大環(huán)數(shù)”是指基態(tài)多邊形中最復(fù)雜的多邊形所具有的空洞數(shù)，建立本文索引時(shí)四叉樹結(jié)點(diǎn)分裂閾值為30. 閾值是由四叉樹索引插入和刪除操作的頻率根據(jù)經(jīng)驗(yàn)來設(shè)定，閾值過大會(huì)使四叉樹查詢接近線性查詢，過小會(huì)造成插入和刪除時(shí)結(jié)點(diǎn)頻繁分裂或合并，增加維護(hù)結(jié)點(diǎn)的時(shí)間開銷. 本文索引建立的主要時(shí)間和空間開銷為包含關(guān)系的建立與存儲(chǔ)，因此索引建立時(shí)間相較于現(xiàn)有四叉樹索引建立，增加了建立包含關(guān)系的時(shí)間開銷，隨著數(shù)據(jù)量的增加索引建立的時(shí)間也會(huì)延長(zhǎng)，但是索引建立時(shí)間總體不長(zhǎng)（本文實(shí)驗(yàn)超過10萬個(gè)多邊形，一般個(gè)人計(jì)算機(jī)建立索引的時(shí)間不超過1min）. 由于存儲(chǔ)包含關(guān)系及內(nèi)環(huán)虛擬多邊形對(duì)象空間開銷較大，平均約占原始數(shù)據(jù)的8%，約為CIF索引的1.5～2倍. 由于索引結(jié)點(diǎn)中的對(duì)象存儲(chǔ)了包含關(guān)系，使索引結(jié)構(gòu)變得復(fù)雜，從本質(zhì)上看，是增加了索引對(duì)象空間數(shù)據(jù)表的列數(shù)，可以通過截?cái)鄶?shù)據(jù)表，增加連接字段來減小索引結(jié)構(gòu)復(fù)雜帶來的影響.

4? ?結(jié)論與討論

多邊形之間的多層嵌套包含關(guān)系反映了地表覆蓋矢量數(shù)據(jù)的復(fù)雜程度，考慮多邊形之間的包含關(guān)系，能顯著提高包含大量空洞的復(fù)雜多邊形增量更新效率. 目前空間數(shù)據(jù)索引一般只用來提高空間查詢效率，不能反映包含空洞的復(fù)雜多邊形及其空洞多邊形之間的嵌套關(guān)系，在地表覆蓋變化沖突檢測(cè)與更新處理中對(duì)于包含成千上萬個(gè)空洞的復(fù)雜多邊形來說，增量更新計(jì)算效率不能滿足實(shí)際應(yīng)用需求. 本文針對(duì)這一問題在已有四叉樹基礎(chǔ)上提出一種存儲(chǔ)拓?fù)浒P(guān)系的四叉樹空間索引方法，為提高結(jié)點(diǎn)搜索效率，該方法根據(jù)結(jié)點(diǎn)中存儲(chǔ)的多邊形對(duì)象與四叉樹結(jié)點(diǎn)相應(yīng)的象限中軸線相交的不同方式分為僅與X正軸、X負(fù)軸、Y正軸、Y負(fù)軸相交以及與XY軸都相交5種類型，根據(jù)這5種類型將多邊形分別排序并存儲(chǔ)在索引結(jié)點(diǎn)的相應(yīng)桶中，通過桶篩選減少索引查詢過程中空間對(duì)象匹配次數(shù)，同時(shí)也避免了多邊形對(duì)象在索引中重復(fù)存儲(chǔ);本文在多邊形對(duì)象中存儲(chǔ)多邊形之間的父子包含關(guān)系，建立存儲(chǔ)復(fù)雜多邊形包含關(guān)系的空間四叉樹索引，并設(shè)計(jì)了存儲(chǔ)包含關(guān)系索引的查詢、插入、刪除等算法;引入內(nèi)環(huán)虛擬多邊形，解決了復(fù)雜多邊形與其空洞多邊形分層存儲(chǔ)導(dǎo)致的復(fù)雜多邊形包含關(guān)系不完整問題. 最后在VS2013平臺(tái)上實(shí)現(xiàn)該索引方法，運(yùn)用提出的索引操作算法開展了基于該索引方法的地表覆蓋矢量數(shù)據(jù)增量更新實(shí)驗(yàn)，實(shí)現(xiàn)了地表覆蓋矢量數(shù)據(jù)批量增量更新，并維護(hù)了索引更新中包含關(guān)系的一致性，驗(yàn)證了所提索引方法的有效性. 實(shí)驗(yàn)結(jié)果表明，利用本文索引對(duì)復(fù)雜地表覆蓋數(shù)據(jù)進(jìn)行空間查詢的效率比現(xiàn)有四叉樹索引效率顯著提高，在本文實(shí)驗(yàn)中增量更新的效率為文獻(xiàn)[10]四叉樹索引方法的2.9～6.2倍，且隨著數(shù)據(jù)量的增加效率提高更明顯.

盡管本文存儲(chǔ)拓?fù)浒P(guān)系的四叉樹空間索引方法是針對(duì)地表覆蓋數(shù)據(jù)更新提出的，該方法同樣可用于土地利用等包含大量復(fù)雜多邊形的應(yīng)用領(lǐng)域;由于本文索引中存儲(chǔ)了復(fù)雜多邊形與其空洞多邊形之間的包含關(guān)系，有利于包含關(guān)系的查詢與統(tǒng)計(jì)分析，如湘江有多少個(gè)島等. 由于本文索引需要建立多邊形間的包含關(guān)系，目前該索引建立時(shí)間要比現(xiàn)有四叉樹索引建立時(shí)間長(zhǎng)，索引更新的效率仍有提升空間;本文實(shí)驗(yàn)假設(shè)在數(shù)據(jù)更新等應(yīng)用中索引結(jié)構(gòu)存儲(chǔ)于內(nèi)存中，尚需探索特大數(shù)據(jù)情況下將索引結(jié)構(gòu)存儲(chǔ)在外存數(shù)據(jù)庫的情形. 因此后續(xù)研究工作主要包括提高索引更新的效率及在特大數(shù)據(jù)情況下本文索引方法的適應(yīng)性探索.

參考文獻(xiàn)

[1]? ? CHEN J，CHEN J，LIAO A P，et al. Global land cover mapping at 30 m resolution：a POK-based operational approach [J]. ISPRS Journal of Photogrammetry and Remote Sensing，2015，103：7—27.

[2]? ? CHEN J，CAO X，PENG S，et al. Analysis and applications of Global Land 30：a review [J]. ISPRS International Journal of Geo-Information，2017，6（8）：230.

[3]? ? GONG P，LIU H ，ZHANG M N，et al. Stable classification with limited sample：transferring a 30-m resolution sample set collected in 2015 to mapping 10-m resolution global land cover in 2017 [J]. Science Bulletin，2019，64（6）：370—373.

[4]? ? 陳斐，陳軍，武昊，等. 基于景觀形狀指數(shù)的地表覆蓋檢驗(yàn)樣本自適應(yīng)抽樣方法[J]. 中國(guó)科學(xué)：地球科學(xué)，2016，46（11）：1413—1425.

CHEN F，CHEN J，WU H，et al. A landscape shape index-based sampling approach for land cover accuracy assessment [J]. Science China Earth Sciences，2016，46（11）：1413—1425. （In Chinese）

[5]? ? 陳軍，武昊，李松年. 全球地表覆蓋領(lǐng)域服務(wù)計(jì)算的研究進(jìn)展--以GlobeLand 30為例[J]. 測(cè)繪學(xué)報(bào)，2017，46（10）：1526—1533.

CHEN J，WU H，LI S N. Research progress of global land domain service computing：take GlobeLand 30 as an example [J]. Acta Geodaetica et Cartographica Sinica，2017，46（10）：1526—1533.（In Chinese）

[6]? ? 魏東升，周曉光. 顧及紋理特征貢獻(xiàn)度的變化影像對(duì)象提取算法[J]. 測(cè)繪學(xué)報(bào)，2017，46（5）：605—613.

WEI D S，ZHOU X G. Changed image objects extraction algorithms considering texture feature contribution [J].Acta Geodaetica et Cartographica Sinica，2017，46（5）：605—613. （In Chinese）

[7]? ? 周曉光，汪紅松，吳志強(qiáng). 引入二維交細(xì)分類型的地表覆蓋矢量數(shù)據(jù)增量更新[J]. 測(cè)繪學(xué)報(bào)，2017，46（1）：114—122.

ZHOU X G，WANG H S，WU Z Q. An incremental updating method for land cover database using refined 2-dimensional intersection type [J].Acta Geodaetica et Cartographica Sinica，2017，46（1）：114—122. （In Chinese）

[8]? ? XING H F，MENG Y，WANG Z X，et al. Exploring geo-tagged photos for land cover validation with deep learning [J]. ISPRS Journal of Photogrammetry and Remote Sensing，2018，141：237—251.

[9]? ? HJALTASON G? R，SAMET H . Speeding up construction of PMR quadtree-based spatial indexes [J]. The VLDB Journal，2002，11（2）：109—137.

[10]? WEI Y，TANAKA S . Performance improvement of MX-CIF quadtree by reducing the query results [J]. International Journal of Computer Theory & Engineering，2012，4（6）：902—906.

[11]? GUTTMAN A . R-trees：a dynamic index structure for spatial searching [C]//? ACM SIGMOD International Conference on Management of Data. Boston：MCM，1984：47—57.

[12]? JIN P Q，XIE X K，WANG N，et al. Optimizing R-tree for flash memory [J]. Expert Systems with Applications，2015，42（10）：4676—4686.

[13]? SELLIS T? K，ROUSSOPOULOS N，F(xiàn)ALOUTSOS C. The R+-tree：a dynamic index for multi-dimensional objects [C]//? International Conference on Very Large Data Bases. Brighton：Margan kaufmann，1987：507—518.

[14]? BECKMANN N，KRIEGEL H P，SCHNEIDER R，et al. The R*-tree：an efficient and robust access method for points and rectangles [C]// ACM SIGMOD international conference on management of data. Atlantic City，New Jersey：ACM，1990：322—331.

[15]? ROUMELIS G，VASSILAKOPOULOS M，CORRAL A，et al. Efficient query processing on large spatial databases：A performance study [J]. Journal of Systems and Software，2017，132：165—185.

[16]? JI C Q，LI Z Y，QU W Y，et al. Scalable nearest neighbor query processing based on inverted grid index [J]. Journal of Network and Computer Applications，2014，44：172—182.

[17]? CHEN H L，CHANG Y I. All-nearest-neighbors finding based on the hilbert curve [J]. Expert Systems with Applications，2011，38（6）：7462—7475.

[18]? 向隆剛，高萌，王德浩，等. Geohash-Trees：一種用于組織大規(guī)模軌跡的自適應(yīng)索引[J]. 武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2019，44（3）：436—442.

XIANG L G，GAO M，WANG D H，et al. Geohash-Trees：an adaptive index which can organize large-scale trajectories [J]. Geomatics and Information Science of Wuhan University，2019，44（3）：436—442.（In Chinese）

[19]? SAMET H . The design and analysis of spatial data structures Addison-Wesley Series in Computer Science [M]. Massachusetts：Addison-Wesley，1990：199—209.

[20]? SAMET H. Foundations of multidimensional and metric data structures[M]. San Mateo：Morgan Kaufmann，2006：466—479.

[21]? KOTHURI R K V，RAVADA S，ABUGOV D. Quadtree and R-tree indexes in oracle spatial：a comparison using GIS data [C]//? Proceedings of the 2002 ACM SIGMOD international conference on Management of data. Madison Wisconsin：ACM，2002：546—577.

[22]? 郭薇，郭菁，胡志勇. 空間數(shù)據(jù)庫索引技術(shù)[M]. 上海：上海交通大學(xué)出版社，2006：100—103.

GUO W，GUO J，HU Z Y. The technology of spatial database index [M]. Shanghai：Shanghai Jiao Tong University Press，2006：100—103.（In Chinese）

[23]? ZIMMERMANN R，KU W S，CHU W C. Efficient query routing in distributed spatial databases [C]//? ACM International Workshop on Geographic Information Systems.Washington D C：ACM，2004：176—183.

[24]? HU Y，RAVADA S，ANDERSON R. Geodetic point-in-polygon query processing in oracle spatial [C]//International Symposium on Spatial and Temporal Databases. Minneapolis：Springer，2011：297—312.

[25]? 張新長(zhǎng)，郭泰圣，唐鐵. 一種自適應(yīng)的矢量數(shù)據(jù)增量更新方法研究[J]. 測(cè)繪學(xué)報(bào)，2012，41（4）：613—619.ZHANG X C，GUO T S，TANG T. An adaptive method for incremental updating of vector data [J].Acta Geodaetica et Cartographica Sinica，2012，41（4）：613—619. （In Chinese）