一種存儲復雜多邊形包含關系的四叉樹索引

汪紅松 周曉光

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

關鍵詞：空間索引;復雜多邊形;包含關系;四叉樹;空間數據管理

中圖分類號：P208? ?? ? ? ? ? ? ? ? ? ? ? ?文獻標志碼：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地表覆蓋數據FROM-GLC10[3]的完成與發布，全球地表覆蓋數據已成為聯合國等國際組織開展全球變化與可持續發展等重大科學研究的基礎數據. 全球地表覆蓋數據的驗證、服務與持續更新成為本領域的研究熱點[4-8].在全球地表覆蓋矢量數據更新方面，周曉光等[7]提出了一種基于二維交細分拓撲關系的地表覆蓋/土地利用數據增量更新方法，但由于地表覆蓋矢量數據中存在大量包含成千上萬個空洞（甚至嵌套空洞）的復雜多邊形，目前空間數據模型中沒有表達復雜多邊形及其空洞之間的包含關系，導致在計算增量多邊形與已存在的復雜多邊形間二維交時存在計算量大、效率低等問題.

GIS中空間數據處理一般包括過濾和精化計算兩個步驟，空間數據索引用來過濾掉大部分無關的目標，使得精化計算僅在少數密切相關目標間進行的效率提升的特殊空間數據結構. 目前，空間數

據索引方法包括傳統矢量數據索引的四叉樹[9-10]、

R樹[11-12]、R+樹[13]、R*樹[14-15]、網格索引[16]、Hilbert R樹[17]等和軌跡數據索引Geohash-Trees[18]等. 上述傳統矢量數據索引方法均采用目標的最小外接矩形（MBR）減小索引結構的存儲量并提高過濾效率. 但是對于復雜多邊形，現有索引方法僅存儲了其外邊界的MBR，不能表達復雜多邊形及其空洞間的包含關系，在空間數據沖突檢測與更新處理中，無關空洞不能通過索引而過濾掉，大量空洞需參與精化計算，是導致計算量大、效率低等問題的根本原因.

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

地表覆蓋矢量數據嵌套復雜，多邊形MBR重疊嚴重，若構建索引R樹結構，則索引性能不佳[15]，同時R樹索引無法避免地重復存儲空間對象，造成空間數據更新時存儲的包含關系一致性維護困難. 處理面目標的四叉樹結構主要有線性四叉樹、PMR四叉樹、CIF四叉樹等結構[9，19-20]. 線性四叉樹用自定義大小的網格映射空間目標[21]，由于地表覆蓋矢量數據面積分布極度不均，難以選擇大小合適的網格，同時索引中空間對象也無法避免重復存儲;PMR四叉樹索引以線段而非以面目標作為整體概念;CIF四叉樹索引以分層的網格映射空間目標[22]，索引結構形態不依賴空間對象插入的順序，不重復存儲空間對象，同時空間數據更新時，結點變更較小[21-23]，本文在CIF四叉樹基礎上提出一種存儲拓撲包含關系的四叉樹空間索引方法.

1? ?包含關系四叉樹索引的建立

1.1? ?多邊形包含關系的表達

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

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

根據以上分析，設CP（Current Polygon）表示當前多邊形，PP（Parent Polygon）為CP的父多邊形，RIPID（Ring in Parent ID）為CP在PP中相應的內環序號，CPL（Children Polygon List ）為CP的子多邊形指針數組，為每個內環建立子多邊形列表，則四叉樹結點中多邊形對象的數據結構可表達為：{CP，PP，RIPID，CPL}.

空間數據往往分圖層構建，且具有鋪蓋特征，其中復雜多邊形與其空洞多邊形可能分別存儲在不同圖層中，導致一個圖層中存在很多空白區域，如圖1中的陰影部分（下同）. 當前圖層只存儲了空白區域的RIP，而無相應多邊形對象. 由于空白區域的RIP不能獨立存儲為多邊形對象，為完整表達該RIP相關的包含關系，本文引入內環虛擬多邊形對象來填滿復雜多邊形內連續的空白區域，即內環虛擬多邊形對象為一個復雜多邊形內空洞邊界構建的虛擬對象，其結構為{CP，PP，-RIPID，?}. 其中CP為內環虛擬多邊形，PP為內環虛擬多邊形的父多邊形，-RIPID為該內環在PP中的序號（用負號來區別于實際存在的多邊形）.

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

規則1? ?P1有內環;

規則2? ?P2的MBR被P1的MBR包含，同時與P1的某一內環r的MBR相等（如圖2中F與rc1）或相交（如圖2中T與rf2）;

規則3? ?P2上任取一頂點在r的環內或環上;

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

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

O（e），若P2的RIP邊數為a，則規則3、4判別的時間開銷為判斷點是否在多邊形內，其復雜度為O（a）[24]. 因此，判別P1包含P2的時間復雜度為O（e+a）.

1.2? ?對現有四叉樹的改進

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

圖3所示為根結點中存儲的多邊形示例，刪除與XY軸均相交的的復雜多邊形后可見與中軸線相交的眾多小圖斑（圖3（b））. 在索引查詢時，當查詢窗口僅與X負軸相交，則仍需要遍歷根結點中所有多邊形，以篩選出目標多邊形，盡管大多數多邊形與查詢窗口相距較遠.

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

根據上述分析，四叉樹索引結點的數據結構可表達為：{NID，NMBR，Subtrees，Depth，PPtr，XYL，XpL，XnL，YpL，YnL}. 其中，NID為結點的ID，NMBR為結點的范圍MBR，Subtrees為子樹（四叉），Depth為結點層次，PPtr為父結點指針，XYL、XpL、XnL、YpL、YnL分別為多邊形與中軸線5種不同相交方式對應桶. 結點中設計指向父結點的指針是為了方便四叉樹中自下而上的遍歷.

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

1）根據空間數據范圍確定根結點MBR并建立

根結點，將與根結點中軸線相交的多邊形對象按照與中軸線相交的類型有序地插入到相應桶內;

2）根據中軸線將結點等分為4個子象限并建立相應子樹，將MBR完全包含在子象限范圍的多邊形存儲在子樹中，并設置子樹指向父結點的線索指針PPtr;

3）對4個子樹遞歸地重復步驟2，直到子樹中多邊形數量達到結點分裂閾值，獲得無包含關系的四叉樹索引;

4）對每個多邊形對象利用PPtr向根搜索并判別父多邊形，同時將該多邊形加入到父多邊形相應內環的CPL指針數組中;

5）掃描CPL，依據內環與子多邊形的對應關系，判別并插入虛擬多邊形對象.

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

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

2? ?存儲包含關系四叉樹索引操作

2.1? ?索引查詢

索引查詢操作是根據查詢條件，查詢與查詢點或區域相交的多邊形（集），查詢操作結果不包括內環虛擬多邊形對象. 點查詢算法的主要步驟為：

1）自根向下搜索四叉樹結點中各桶的MBR是

否包含該查詢點，若包含，則進一步判斷桶內多邊形MBR是否包含查詢點，構造候選多邊形集;

2）遍歷候選集查找第一個滿足查詢點在外環內的多邊形P;

3）遍歷候選集中是否存在P的子多邊形且滿足查詢點在該子多邊形環外內，則該子多邊形為新的P;

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

區域查詢算法主要步驟為：

1）用與點查詢相似方法構造候選多邊形集合;

2）遍歷候選多邊形，將外環與查詢窗口相交的多邊形（內環虛擬多邊形除外）加入查詢結果集;

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

4）其他候選多邊形若窗口任意一點在其外環內且不在其候選集中的子多邊形（或內環虛擬多邊形）RIP內，則加入到查詢結果集.

查詢算法一方面通過桶MBR的篩選，能合理避免不必要的索引搜索開銷，另一方面通過存儲的多邊形間父子包含關系，避免對候選集中多邊形外環及內環逐一判別點在環內的算法開銷.

2.2? ?索引中刪除多邊形對象

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

從四叉樹中刪除多邊形包括兩個任務：1）刪除該多邊形的子多邊形和父多邊形的包含關系;2）刪除該多邊形對象，若該多邊形有父多邊形，則建立父多邊形的內環虛擬多邊形對象并插入到索引中.

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

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

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

3）從當前結點中刪除g，若父結點不為空，則以RIP構建虛擬多邊形對象并插入索引;

4）若g所在結點為葉結點，則向上遞歸進行結點合并操作.

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

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

2.3? ?索引中插入多邊形對象

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

1）建立多邊形g的包含關系;

2）在四叉樹索引中查詢應插入的結點，并將多邊形g插入到相應的桶中;

3）若g內有更新產生的內環，則判別是否需要從索引中刪除相關的虛擬多邊形對象;

4）若插入的結點為葉結點，則判斷并處理插入操作可能引起的結點分裂.

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

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

3? ?實驗與比較

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

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

4? ?結論與討論

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

盡管本文存儲拓撲包含關系的四叉樹空間索引方法是針對地表覆蓋數據更新提出的，該方法同樣可用于土地利用等包含大量復雜多邊形的應用領域;由于本文索引中存儲了復雜多邊形與其空洞多邊形之間的包含關系，有利于包含關系的查詢與統計分析，如湘江有多少個島等. 由于本文索引需要建立多邊形間的包含關系，目前該索引建立時間要比現有四叉樹索引建立時間長，索引更新的效率仍有提升空間;本文實驗假設在數據更新等應用中索引結構存儲于內存中，尚需探索特大數據情況下將索引結構存儲在外存數據庫的情形. 因此后續研究工作主要包括提高索引更新的效率及在特大數據情況下本文索引方法的適應性探索.

參考文獻

[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]? ? 陳斐，陳軍，武昊，等. 基于景觀形狀指數的地表覆蓋檢驗樣本自適應抽樣方法[J]. 中國科學：地球科學，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]? ? 陳軍，武昊，李松年. 全球地表覆蓋領域服務計算的研究進展--以GlobeLand 30為例[J]. 測繪學報，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]? ? 魏東升，周曉光. 顧及紋理特征貢獻度的變化影像對象提取算法[J]. 測繪學報，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]? ? 周曉光，汪紅松，吳志強. 引入二維交細分類型的地表覆蓋矢量數據增量更新[J]. 測繪學報，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，FALOUTSOS 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：一種用于組織大規模軌跡的自適應索引[J]. 武漢大學學報（信息科學版），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]? 郭薇，郭菁，胡志勇. 空間數據庫索引技術[M]. 上海：上海交通大學出版社，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]? 張新長，郭泰圣，唐鐵. 一種自適應的矢量數據增量更新方法研究[J]. 測繪學報，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）