基于多層Voronoi圖索引的非點(diǎn)型空間對(duì)象區(qū)域查詢方法研究

明 梓，劉 偉，李 旸，崔俊杰，劉 剛，李佳惠，雷夢(mèng)婷

（1.湖北工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，湖北 武漢 430068；2.長(zhǎng)江信達(dá)軟件技術(shù)（武漢）有限責(zé)任公司，湖北 武漢 430014；3.中國地質(zhì)大學(xué)（武漢）地理與信息工程學(xué)院；4.中國地質(zhì)大學(xué)（武漢）計(jì)算機(jī)學(xué)院，湖北 武漢 430078；5.湖北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430068）

0 引言

城市化進(jìn)程的加快帶來了交通擁堵、空間環(huán)境惡劣等問題，給我國智慧城市的建設(shè)帶來了挑戰(zhàn)［1-4］。合理開發(fā)與利用城市地理空間大數(shù)據(jù)，借助物聯(lián)網(wǎng)和人工智能等技術(shù)對(duì)城市地理空間資源進(jìn)行智能管控與高效調(diào)度是解決上述問題的有效途徑。在面向城市地理空間大數(shù)據(jù)的地理信息系統(tǒng)（Geographic Information System，GIS）建設(shè)中，高效的空間查詢技術(shù)是關(guān)鍵基礎(chǔ)［5-9］。其中，區(qū)域查詢方法是應(yīng)用最廣泛的一類查詢方法，可以快速檢索到指定區(qū)域內(nèi)包含的全部地理空間對(duì)象（例如建筑、植被、公共設(shè)施、車輛等），幫助城市管理者了解城市地物的分布情況，從而為其提供決策支持。

基于空間邊界約束的查詢通常被稱為空間區(qū)域查詢，即從該數(shù)據(jù)庫中檢索出一個(gè)指定區(qū)域內(nèi)的所有數(shù)據(jù)對(duì)象，這個(gè)目標(biāo)區(qū)域可以是任何形狀的封閉幾何圖形。目前主流區(qū)域查詢算法均基于R-tree 提出，但由于R-tree 在面對(duì)大規(guī)模、非均勻分布的城市空間大數(shù)據(jù)時(shí)會(huì)出現(xiàn)節(jié)點(diǎn)重疊、結(jié)構(gòu)失衡等一系列問題，以R-tree 索引為基礎(chǔ)的區(qū)域查詢算法很難有理想表現(xiàn)。因此，MVD（Multi-layer Voronoi Diagrams）索引被提出，其通過多層Voronoi 網(wǎng)絡(luò)結(jié)構(gòu)替代傳統(tǒng)樹形結(jié)構(gòu)，有效規(guī)避了上述問題［5］。以MVD 為基礎(chǔ)的區(qū)域查詢算法在面對(duì)城市空間大數(shù)據(jù)時(shí)展現(xiàn)出更高的查詢效率（即查詢算法的響應(yīng)速度），但其無法直接對(duì)非點(diǎn)型數(shù)據(jù)進(jìn)行索引，因此基于MVD 的區(qū)域查詢方法不支持非點(diǎn)型空間數(shù)據(jù)。

針對(duì)上述問題，本文基于MVD 索引提出一種針對(duì)非點(diǎn)型空間對(duì)象的區(qū)域查詢技術(shù)框架：首先通過最小外包圓（Minimum Bounding Circle，MBC）對(duì)空間對(duì)象進(jìn)行擬合，實(shí)現(xiàn)MVD 索引對(duì)非點(diǎn)型空間對(duì)象的存儲(chǔ)管理；然后根據(jù)空間對(duì)象最小外包圓的半徑上界對(duì)查詢區(qū)域進(jìn)行邊界拓展，實(shí)現(xiàn)MVD 索引對(duì)非點(diǎn)型空間對(duì)象的區(qū)域查詢，進(jìn)而提出MVD-Polygon 算法。為進(jìn)一步優(yōu)化MVD-Polygon 算法的查詢效率，采用空間對(duì)象尺度對(duì)數(shù)據(jù)進(jìn)行分級(jí)管理，從而加速查詢過程，并將優(yōu)化后的MVD-Polygon 命名為MVDPolygon-Grade。為驗(yàn)證該方案的有效性，將MVD-Polygon、MVD-Polygon-Grade 與基于R-tree 的主流區(qū)域查詢算法Multi-step 進(jìn)行性能比較，結(jié)果表明MVD-Polygon 算法擁有更高的查詢效率。

1 相關(guān)研究

空間區(qū)域查詢最早由Willard［10］提出，并提供了一種以O(shè)(nlog64)復(fù)雜度求解的方案，其中n為數(shù)據(jù)庫中的數(shù)據(jù)總量；而后，Paterson 等［11］基于B-tree 提出一種計(jì)算復(fù)雜度為O(k·logn+s)的求解方案，其中k為多邊形邊的數(shù)量，s為結(jié)果集大小。自R-tree 索引被提出后，絕大多數(shù)區(qū)域查詢方法都開始采用該索引作為基礎(chǔ)來實(shí)現(xiàn)。為減少PIP（Point in Polygon）驗(yàn)證次數(shù)，Kriegel 等［12］基于R-tree 索引提出一種通過兩級(jí)過濾策略實(shí)現(xiàn)的空間區(qū)域查詢算法Multi-step，該算法通過查詢區(qū)域的外包近似形從R-tree 中檢索出一個(gè)候選集，然后對(duì)候選集中的對(duì)象逐一過濾，篩選出最終結(jié)果集。R-tree 內(nèi)部的基本單元都是空間正交矩形，而正交矩形之間的空間關(guān)系運(yùn)算非常簡(jiǎn)單快速，因此一般情況下都是利用正交的最小外包矩形（Minimum Bounding Rectangle，MBR）來構(gòu)建查詢區(qū)域的近似形。在Oracle Spatial 組建中，區(qū)域查詢也是基于R-tree 實(shí)現(xiàn)的，但其不需要利用空間近似形進(jìn)行初次過濾，而是直接利用查詢范圍進(jìn)行檢索［13］。在這種區(qū)域查詢算法的執(zhí)行過程中，雖然部分節(jié)點(diǎn)與查詢區(qū)域之間的空間拓?fù)潢P(guān)系運(yùn)算成本會(huì)有所增加，但總體I/O 成本有效降低。

城市地理空間數(shù)據(jù)的多中心非均勻分布會(huì)加劇Rtree 索引的節(jié)點(diǎn)重疊，因此在面向城市地理空間大數(shù)據(jù)的GIS 系統(tǒng)中，基于R-tree 實(shí)現(xiàn)的區(qū)域查詢算法需要訪問大量索引中間層節(jié)點(diǎn)，并產(chǎn)生大量冗余空間關(guān)系驗(yàn)證，進(jìn)而導(dǎo)致基于R-tree 的Multi-step 區(qū)域查詢算法在面對(duì)海量對(duì)象、空間關(guān)系復(fù)雜的場(chǎng)景中存在查詢效率較低的問題。為進(jìn)一步提升復(fù)雜場(chǎng)景下的算法查詢效率，Li等［14］基于復(fù)合型索引VoR-tree 提出一種利用Voronoi 圖實(shí)現(xiàn)的區(qū)域查詢方法Voronoi-Region，并將該方遷移至高性能的多層網(wǎng)絡(luò)結(jié)構(gòu)索引MVD 中［5］。借助MVD 的非樹形結(jié)構(gòu)，該算法在避免訪問大量中間節(jié)點(diǎn)的同時(shí)削減了絕大部分冗余數(shù)據(jù)點(diǎn)的訪問和驗(yàn)證，有效提升了海量對(duì)象以及復(fù)雜空間關(guān)系場(chǎng)景中針對(duì)點(diǎn)型數(shù)據(jù)的區(qū)域查詢效率。然而，Voronoi圖的構(gòu)建需要以一個(gè)離散點(diǎn)集合為基礎(chǔ)，以Voronoi 圖為基礎(chǔ)部件的MVD 索引僅支持點(diǎn)型數(shù)據(jù)管理，即相對(duì)應(yīng)的區(qū)域查詢方法無法適用于非點(diǎn)型數(shù)據(jù)檢索。

為此，本文基于MVD 索引提出針對(duì)非點(diǎn)型數(shù)據(jù)的管理方式和相應(yīng)的區(qū)域查詢算法，以解決MVD 索引不支持非點(diǎn)型數(shù)據(jù)管理以及其對(duì)應(yīng)的區(qū)域查詢算法無法對(duì)非點(diǎn)型數(shù)據(jù)進(jìn)行區(qū)域查詢的問題，進(jìn)而改進(jìn)目前主流算法在海量對(duì)象與復(fù)雜空間關(guān)系場(chǎng)景下對(duì)非點(diǎn)型數(shù)據(jù)進(jìn)行區(qū)域查詢時(shí)效率不足的問題。

2 基于邊界擴(kuò)展的MVD區(qū)域查詢技術(shù)

2.1 總體技術(shù)框架設(shè)計(jì)

基于MVD 索引實(shí)現(xiàn)針對(duì)非點(diǎn)型空間數(shù)據(jù)的高性能區(qū)域查詢方法需要解決兩個(gè)重點(diǎn)問題：第一是如何實(shí)現(xiàn)MVD 索引對(duì)非點(diǎn)型空間對(duì)象的存儲(chǔ)管理？本文基于MVD索引的點(diǎn)對(duì)象與非點(diǎn)型空間對(duì)象之間的關(guān)系構(gòu)建起兩種映射關(guān)系，完成對(duì)非點(diǎn)型空間對(duì)象的管理；第二是如何基于MVD 索引設(shè)計(jì)針對(duì)非點(diǎn)型空間對(duì)象的區(qū)域查詢方法？本文采用引入緩沖區(qū)的方法構(gòu)建候選集，并對(duì)候選集中的對(duì)象進(jìn)行空間關(guān)系驗(yàn)證，得到最終結(jié)果集。同時(shí)基于初始查詢邊界拓展查詢邊界，實(shí)現(xiàn)MVD 索引對(duì)非點(diǎn)型空間對(duì)象的查詢，并基于空間對(duì)象尺度的數(shù)據(jù)分級(jí)方法加速查詢過程?？傮w技術(shù)框架見圖1（彩圖掃OSID 碼可見，下同）。

Fig.1 Overall technical framework圖1 總體技術(shù)框架

2.2 非點(diǎn)型空間對(duì)象存儲(chǔ)管理方法

針對(duì)非點(diǎn)型空間對(duì)象的管理方式需注意兩個(gè)方面：①M(fèi)VD 索引結(jié)構(gòu)是以點(diǎn)對(duì)象為基礎(chǔ)構(gòu)建的，非點(diǎn)型空間對(duì)象需基于MVD 索引結(jié)構(gòu)進(jìn)行管理；②MVD 索引結(jié)構(gòu)管理非點(diǎn)型空間對(duì)象時(shí)需完整地存儲(chǔ)非點(diǎn)型對(duì)象數(shù)據(jù)。

針對(duì)第一個(gè)方面，MVD 索引結(jié)構(gòu)以點(diǎn)對(duì)象為基礎(chǔ)構(gòu)建，需要選擇某個(gè)點(diǎn)來代替非點(diǎn)型空間對(duì)象構(gòu)建索引結(jié)構(gòu)。本文選擇非點(diǎn)型空間對(duì)象的質(zhì)心代替整個(gè)對(duì)象構(gòu)建MVD 索引結(jié)構(gòu)，構(gòu)建質(zhì)心與整個(gè)對(duì)象一對(duì)一的映射關(guān)系。非點(diǎn)型空間對(duì)象與質(zhì)點(diǎn)映射關(guān)系如圖2所示。

Fig.2 Mapping relationship between non-point spatial object and centroid圖2 非點(diǎn)型空間對(duì)象與質(zhì)心映射關(guān)系

針對(duì)第二個(gè)方面，非點(diǎn)型空間對(duì)象包含眾多數(shù)據(jù)，如對(duì)象的邊界線數(shù)據(jù)、尺度數(shù)據(jù)、屬性數(shù)據(jù)等。在完成這些數(shù)據(jù)的存儲(chǔ)后，本文根據(jù)質(zhì)心與這些數(shù)據(jù)的關(guān)聯(lián)關(guān)系構(gòu)建一對(duì)多的映射關(guān)系。

以上兩種映射關(guān)系可以通過非點(diǎn)型空間對(duì)象的質(zhì)心ID 進(jìn)行關(guān)聯(lián)。其中，第一種映射關(guān)系通過非點(diǎn)型空間對(duì)象的質(zhì)心構(gòu)建MVD 索引，然后通過針對(duì)點(diǎn)對(duì)象的空間查詢方法進(jìn)行區(qū)域查詢，可以得到非點(diǎn)型空間對(duì)象的質(zhì)心構(gòu)成的點(diǎn)集；第二種映射關(guān)系根據(jù)點(diǎn)集中的點(diǎn)對(duì)象ID 與其對(duì)應(yīng)的非點(diǎn)型空間對(duì)象ID 的映射關(guān)系即可查詢到整個(gè)非點(diǎn)型空間對(duì)象的全部數(shù)據(jù)。

2.3 基于邊界擴(kuò)展技術(shù)的MVD索引區(qū)域查詢方法

基于邊界擴(kuò)展技術(shù)的區(qū)域查詢方法總體流程如圖3所示。該方法主要包含兩個(gè)核心技術(shù)，分別為基于MBC半徑的查詢區(qū)域邊界擴(kuò)展方法和基于擴(kuò)展邊界的候選集驗(yàn)證方法。基于MBC 半徑的查詢區(qū)域邊界擴(kuò)展方法的主要思路為通過引入緩沖區(qū)來增大區(qū)域查詢范圍，使候選集包含所有查詢結(jié)果；基于擴(kuò)展邊界的候選集驗(yàn)證方法的主要思路為通過對(duì)候選集中的對(duì)象進(jìn)行空間關(guān)系驗(yàn)證來篩選出最終結(jié)果集。

Fig.3 Overall process of region query method based on boundary extension technology圖3 基于邊界擴(kuò)展技術(shù)的區(qū)域查詢方法總體流程

2.3.1 基于MBC半徑的查詢區(qū)域邊界擴(kuò)展方法

選擇非點(diǎn)型空間對(duì)象的質(zhì)心構(gòu)建MVD 索引后，如果僅直接按照將質(zhì)點(diǎn)視為整個(gè)非點(diǎn)型空間對(duì)象的思路進(jìn)行區(qū)域查詢，則會(huì)造成質(zhì)點(diǎn)在查詢區(qū)域外，但其實(shí)際對(duì)應(yīng)的非點(diǎn)型空間對(duì)象在查詢區(qū)域內(nèi)的情況，本文將其稱為漏檢問題。針對(duì)該問題，本文在原有區(qū)域查詢邊界的基礎(chǔ)上引入緩沖區(qū)來構(gòu)建候選集。為表述方便，定義以下概念：①空間對(duì)象尺度，指空間對(duì)象最小外包圓的半徑值，用R 表示，點(diǎn)對(duì)象的尺度為零；②緩沖區(qū)尺度，指構(gòu)建緩沖區(qū)過程中在查詢邊界外側(cè)所作的平行線與查詢邊界的垂直距離，用L表示；③數(shù)據(jù)集尺度，數(shù)據(jù)集中全體空間對(duì)象尺度的最大值代表該數(shù)據(jù)集的尺度，即Rmax=Max{R1，R2，R3，…，Rn}，用Rmax表示。

以緩沖區(qū)邊界為基礎(chǔ)執(zhí)行對(duì)點(diǎn)對(duì)象的區(qū)域查詢方法，得到由質(zhì)心構(gòu)成的點(diǎn)集，點(diǎn)集中的質(zhì)心所對(duì)應(yīng)的非點(diǎn)型空間對(duì)象構(gòu)建成了候選集。只要緩沖區(qū)邊界可以包含所有結(jié)果，便可以避免漏檢現(xiàn)象。因此，在初始區(qū)域查詢邊界的基礎(chǔ)上引入何種尺度的緩沖區(qū)是關(guān)鍵問題［15-17］，基于極限思想，當(dāng)緩沖區(qū)尺度大于或等于數(shù)據(jù)集中最大尺度的非點(diǎn)型空間對(duì)象時(shí)，緩沖區(qū)邊界恰好包含所有結(jié)果。以圖4為例，尺度最大的非點(diǎn)型空間對(duì)象為4 號(hào)，其質(zhì)心為p點(diǎn)，尺度為Rmɑx，如果僅看區(qū)域查詢邊界，p點(diǎn)在區(qū)域查詢邊界之外，當(dāng)緩沖區(qū)尺度L等于Rmɑx時(shí)，緩沖區(qū)邊界可以包含所有區(qū)域查詢的結(jié)果（p點(diǎn)在緩沖區(qū)邊界內(nèi)），這些結(jié)果構(gòu)成了針對(duì)非點(diǎn)型空間對(duì)象的區(qū)域查詢算法的候選集。

Fig.4 Schematic diagram of maximum value of buffer scale圖4 緩沖區(qū)尺度極大值示意圖

綜上可知，基于初始查詢邊界引入合適尺度的緩沖區(qū)便可使所有結(jié)果包含在緩沖區(qū)范圍內(nèi)。對(duì)于區(qū)域查詢邊界，分別在其外側(cè)作距邊界線一定距離的平行線可生成緩沖區(qū)邊界［18］。根據(jù)查詢區(qū)域原始邊界的頂點(diǎn)坐標(biāo)和緩沖區(qū)尺度可以求得每個(gè)原始頂點(diǎn)到其在緩沖區(qū)邊界上對(duì)應(yīng)頂點(diǎn)間的向量d，從而得到緩沖區(qū)邊界上所有頂點(diǎn)的坐標(biāo)。每個(gè)頂點(diǎn)對(duì)應(yīng)的向量d的計(jì)算步驟如下：

（1）構(gòu)建單位向量。如圖5 所示，對(duì)于當(dāng)前區(qū)域查詢邊界上的點(diǎn)p來說，其與左右相鄰點(diǎn)n、m構(gòu)成兩個(gè)向量，設(shè)向量為n，向量為m，其單位向量分別為a和b。

Fig.5 Schematic diagram of buffer intersectionc圖5 緩沖區(qū)交點(diǎn)示意圖

（2）計(jì)算擴(kuò)大后的向量。計(jì)算出單位向量后，由于兩個(gè)方向的向量大小模長(zhǎng)均為1，將a和b向量相加并取反得到外擴(kuò)方向上的單位向量c。

（3）計(jì)算緩沖區(qū)邊界上的交點(diǎn)。緩沖區(qū)尺度為L(zhǎng)，取向量c的反向向量-c與m的角度，進(jìn)而計(jì)算向量-c與向量m的距離dis。計(jì)算dis與L的比值，根據(jù)比值計(jì)算向量c方向上的目標(biāo)向量d，計(jì)算方法見式（1）。最后根據(jù)兩個(gè)向量求出目標(biāo)點(diǎn)q。

基于數(shù)據(jù)集尺度引入對(duì)應(yīng)尺度的緩沖區(qū)，然后利用緩沖區(qū)邊界對(duì)空間對(duì)象集對(duì)應(yīng)的質(zhì)心點(diǎn)集執(zhí)行范圍查詢，即可得到充分包含所有結(jié)果集對(duì)象的候選集。具體步驟為：①獲取區(qū)域查詢范圍邊界；②基于原始區(qū)域查詢邊界引入數(shù)據(jù)集對(duì)應(yīng)的緩沖區(qū)，得到緩沖區(qū)邊界；③基于緩沖區(qū)邊界進(jìn)行針對(duì)點(diǎn)數(shù)據(jù)的區(qū)域查詢，得到質(zhì)心集合；④基于“2.2”節(jié)中的第一種映射關(guān)系即可通過質(zhì)心集合中的質(zhì)心ID 查詢到質(zhì)心對(duì)應(yīng)的非點(diǎn)型空間對(duì)象，這些非點(diǎn)型空間對(duì)象構(gòu)成了候選集。

2.3.2 基于擴(kuò)展邊界的候選集驗(yàn)證方法

當(dāng)候選集構(gòu)建完成后，需要對(duì)其中的對(duì)象進(jìn)行過濾，以得到最終結(jié)果集，其中過濾主要是驗(yàn)證結(jié)果集中非點(diǎn)型空間對(duì)象與區(qū)域查詢邊界之間空間關(guān)系的過程。候選集中的非點(diǎn)型空間對(duì)象可分為兩類：第一類是質(zhì)心在區(qū)域查詢邊界內(nèi)的對(duì)象，第二類是質(zhì)心在區(qū)域查詢邊界與緩沖區(qū)邊界之間的對(duì)象。如圖6 所示，1、2、3 號(hào)對(duì)象為第一類對(duì)象；紅點(diǎn)處為第二類對(duì)象。

Fig.6 Schematic diagram of two types of non-point spatial objects圖6 兩種非點(diǎn)型空間對(duì)象示意圖

針對(duì)第一類對(duì)象進(jìn)行空間關(guān)系驗(yàn)證，如果某個(gè)空間對(duì)象的質(zhì)心在區(qū)域查詢邊界內(nèi)，說明這個(gè)對(duì)象一定與查詢邊界存在相交或包含關(guān)系，屬于區(qū)域查詢的結(jié)果集，只需要進(jìn)行一次針對(duì)點(diǎn)對(duì)象的區(qū)域查詢即可得到由質(zhì)心構(gòu)成的點(diǎn)集，點(diǎn)集中的點(diǎn)所對(duì)應(yīng)的非點(diǎn)型空間對(duì)象即為構(gòu)成結(jié)果集的對(duì)象。

針對(duì)第二類對(duì)象進(jìn)行空間關(guān)系驗(yàn)證，只需要判斷是否至少滿足以下兩個(gè)條件之一：①該空間對(duì)象至少存在一個(gè)邊界頂點(diǎn)在查詢區(qū)域內(nèi)部（避免邊的重合）；②該空間對(duì)象的邊界與查詢區(qū)域邊界相交。本文采用引射線法判斷二者是否相交［19-20］，如果存在相交關(guān)系，則將其納入結(jié)果集中。

2.3.3 算法步驟

基于MVD 索引的針對(duì)非點(diǎn)型空間對(duì)象的區(qū)域查詢算法步驟為：

2.4 基于空間對(duì)象尺度分級(jí)的索引構(gòu)建策略

由上文可知，基于初始查詢邊界引入合適尺度的緩沖區(qū)便可將所有結(jié)果包含在緩沖區(qū)范圍內(nèi)。如果數(shù)據(jù)集中的非點(diǎn)型空間對(duì)象尺度相近，引入緩沖區(qū)進(jìn)行區(qū)域查詢后候選集中只包含少量冗余對(duì)象。然而在城市空間查詢場(chǎng)景中，數(shù)據(jù)集中的非點(diǎn)型空間對(duì)象尺度不一定相近，例如一個(gè)城市的人工湖、大型商場(chǎng)、一個(gè)電話亭的尺度完全不在一個(gè)數(shù)量級(jí)，根據(jù)城市內(nèi)最大尺度對(duì)象的尺度引入緩沖區(qū)后，區(qū)域查詢的候選集中會(huì)包含大量冗余對(duì)象。如果根據(jù)尺度對(duì)數(shù)據(jù)集中的對(duì)象進(jìn)行分類，手動(dòng)將尺度相近的對(duì)象分在同一個(gè)數(shù)據(jù)集中，例如將電話亭、汽車等尺度在米級(jí)別的對(duì)象分到一個(gè)數(shù)據(jù)集中，將商場(chǎng)、學(xué)校等百米級(jí)別的對(duì)象分到另一個(gè)數(shù)據(jù)集中，以此構(gòu)成若干個(gè)子數(shù)據(jù)集，并分別引入對(duì)應(yīng)尺度的緩沖區(qū)進(jìn)行查詢，則可有效減少候選集中的冗余對(duì)象。

如圖7 所示，以澳門市建筑輪廓的一部分為研究對(duì)象構(gòu)建各尺度子數(shù)據(jù)集的候選集，建筑對(duì)象構(gòu)成了數(shù)據(jù)集，將數(shù)據(jù)集內(nèi)的對(duì)象手動(dòng)分為大、中、小尺寸的3 個(gè)子數(shù)據(jù)集，并分別引入相應(yīng)尺度的緩沖區(qū)。其中，圖7（a）為數(shù)據(jù)集未進(jìn)行尺度劃分的情況，引入整個(gè)數(shù)據(jù)集中尺度最大的空間對(duì)象的尺度（圖中5 號(hào)對(duì)象的尺度）作為緩沖區(qū)邊界，質(zhì)心在緩沖區(qū)內(nèi)的所有非點(diǎn)型空間對(duì)象均被納入到候選集中，共包含20 個(gè)對(duì)象，其中1、2、3、4 號(hào)對(duì)象為區(qū)域查詢的最終結(jié)果。圖7（b）、（c）、（d）為3 個(gè)不同尺度的子數(shù)據(jù)集引入對(duì)應(yīng)尺度緩沖區(qū)后的結(jié)果。子候選集中的對(duì)象個(gè)數(shù)分別為6、2、0，對(duì)子候選集取并集構(gòu)成最終候選集，共包含8 個(gè)對(duì)象，且1、2、3、4 號(hào)對(duì)象均包含其中?？梢钥闯?，對(duì)數(shù)據(jù)集進(jìn)行分級(jí)預(yù)處理可有效減少候選集中的冗余對(duì)象。

Fig.7 Schematic diagram of candidate subset construction of sub data sets of all scales圖7 各尺度子數(shù)據(jù)集候選集構(gòu)建示意圖

3 實(shí)驗(yàn)方法與結(jié)果分析

為驗(yàn)證本文提出的針對(duì)非點(diǎn)型空間對(duì)象的區(qū)域查詢算法MVD-Polygon-Grade（以下簡(jiǎn)稱MPG 算法）的性能，以及基于空間對(duì)象尺度的數(shù)據(jù)分級(jí)管理方案的查詢效率，以基于R-tree 的Multi-step 算法（以下簡(jiǎn)稱MS 算法）和MVD-Polygon（以下簡(jiǎn)稱MP 算法）算法為對(duì)照進(jìn)行評(píng)估實(shí)驗(yàn)。本實(shí)驗(yàn)旨在比較3 種算法的時(shí)間效率，即算法完成一次查詢所需要的時(shí)間，所需時(shí)間越少，算法效率越高。為減少誤差，實(shí)驗(yàn)結(jié)果經(jīng)過50次運(yùn)行后取算數(shù)平均值得到。

3.1 實(shí)驗(yàn)環(huán)境配置

實(shí)驗(yàn)環(huán)境主要包括軟件和硬件兩個(gè)方面，詳細(xì)配置如表1所示。

3.2 數(shù)據(jù)集

基于尺度相近的對(duì)象放到同一個(gè)子數(shù)據(jù)集的原則，本研究根據(jù)澳門市12 482 個(gè)建筑輪廓的面數(shù)據(jù)將城市建筑分為5類，構(gòu)建5個(gè)子數(shù)據(jù)集。具體信息見表2。

Table 2 Information of sub datasets at different scales表2 不同尺度子數(shù)據(jù)集信息

3.3 結(jié)果分析

如圖8 所示，澳門市建筑輪廓數(shù)據(jù)集包含12 482 個(gè)建筑輪廓的面數(shù)據(jù)，這些面數(shù)據(jù)共由225 807 個(gè)邊界點(diǎn)構(gòu)成，平均每個(gè)面數(shù)據(jù)由18 個(gè)點(diǎn)表示，符合非點(diǎn)型空間對(duì)象的特征。

Fig.8 Outline of buildings in Macao圖8 澳門市建筑輪廓

為研究區(qū)域查詢邊界的規(guī)則程度對(duì)算法效率的影響，分別構(gòu)建頂點(diǎn)為4～6 個(gè)和20～30 個(gè)的多邊形作為區(qū)域查詢邊界，兩組多邊形分別構(gòu)建50 個(gè)。為減少查詢面積對(duì)實(shí)驗(yàn)結(jié)果的影響，本組實(shí)驗(yàn)保證查詢區(qū)域邊界的最小外包圓面積相同，查詢面積依次為3 km2、5 km2、8 km2、12 km2、16 km2。由圖9 可以看出，無論區(qū)域查詢邊界是否規(guī)則，在相同查詢面積下，MPG 算法比MS算法和MP 算法具有更高的效率，但MPG 算法比MS 算法更易受到區(qū)域查詢邊界規(guī)則程度的影響，區(qū)域查詢邊界越復(fù)雜，MPG 算法效率下降得越快。這是由于在MPG 算法的結(jié)果集構(gòu)建過程中，第一類空間對(duì)象是基于高效MVD 針對(duì)點(diǎn)數(shù)據(jù)的區(qū)域查詢算法而來，本身就屬于結(jié)果集，只需要很低的時(shí)間成本即可完成第一類空間對(duì)象的確定；而判斷第二類空間對(duì)象是否屬于結(jié)果集需要依次對(duì)其進(jìn)行空間關(guān)系驗(yàn)證，相對(duì)耗時(shí)，且區(qū)域查詢邊界越復(fù)雜，空間關(guān)系驗(yàn)證所需時(shí)間成本越高；區(qū)域查詢面積越小，第二類空間對(duì)象占整個(gè)候選集的比例越大?；谝陨显颍琈PG 算法基于空間對(duì)象尺度對(duì)數(shù)據(jù)進(jìn)行分級(jí)管理，以確保第二類空間對(duì)象很少。MP 算法沒有基于空間對(duì)象尺度對(duì)數(shù)據(jù)進(jìn)行分級(jí)管理，導(dǎo)致有大量第二類空間對(duì)象需要進(jìn)行空間關(guān)系驗(yàn)證，因此與MS 算法相比，MP 算法在區(qū)域查詢面積較小時(shí)并未體現(xiàn)出明顯優(yōu)勢(shì)。隨著區(qū)域查詢面積的增大，第二類空間對(duì)象占候選集對(duì)象的比例逐漸降低，MP 算法效率逐漸接近MPG 算法。

Fig.9 The influence of the rule degree of region query boundary on the efficiency of region query圖9 區(qū)域查詢邊界規(guī)則程度對(duì)區(qū)域查詢效率的影響

為驗(yàn)證查詢區(qū)域面積對(duì)算法效率的影響，本組實(shí)驗(yàn)的區(qū)域查詢邊界形狀設(shè)置為正交矩形，查詢位置隨機(jī)，查詢區(qū)域面積分別為3 km2、5 km2、8 km2、12 km2、16 km2，分別占整個(gè)數(shù)據(jù)分布區(qū)域的6.2%、10.4%、16.7%、25%、33.3%，每種面積下的查詢次數(shù)均為50 次，取算數(shù)平均值作為最終結(jié)果。由圖10 可以看出，無論何種查詢面積，MPG 算法均比MS 算法和MP 算法有更高的查詢效率。在區(qū)域查詢面積較小的情況下，MP 算法和MS 算法的效率并未表現(xiàn)出顯著差異；在區(qū)域查詢面積較大的情況下，MP 算法的效率接近于MPG 算法，強(qiáng)于MS算法。

Fig.10 The influence of query area on the efficiency of region query圖10 查詢區(qū)域面積對(duì)區(qū)域查詢效率的影響

4 結(jié)語

為合理開發(fā)與利用城市地理空間大數(shù)據(jù)，本文針對(duì)MVD 索引只能管理點(diǎn)型數(shù)據(jù)而無法直接針對(duì)非點(diǎn)型數(shù)據(jù)進(jìn)行區(qū)域查詢的問題，設(shè)計(jì)提出了一種基于邊界擴(kuò)展技術(shù)的區(qū)域查詢算法實(shí)現(xiàn)框架。該框架通過最小外包圓對(duì)空間對(duì)象進(jìn)行擬合，基于MVD 索引實(shí)現(xiàn)非點(diǎn)型空間對(duì)象的區(qū)域查詢，并基于空間對(duì)象尺度對(duì)數(shù)據(jù)進(jìn)行分級(jí)管理以提高查詢效率。利用澳門市城市建筑輪廓數(shù)據(jù)進(jìn)行驗(yàn)證實(shí)驗(yàn)，結(jié)果表明，在相同查詢面積、查詢邊界復(fù)雜程度條件下，本文提出的MVD-Polygon-Grade 算法比Multistep 算法和MVD-Polygon 算法查詢效率更高，且數(shù)據(jù)規(guī)模越大、查詢面積越大，數(shù)據(jù)尺度分級(jí)層次越明顯，MVDPolygon-Grade 算法的區(qū)域查詢效率越高。本研究提出了從點(diǎn)對(duì)象拓展到非點(diǎn)型空間對(duì)象的通用數(shù)據(jù)管理思路和區(qū)域查詢方法，為進(jìn)一步挖掘現(xiàn)有索引結(jié)構(gòu)的數(shù)據(jù)管理潛力提供了支撐。然而該方法仍存在改進(jìn)空間：①M(fèi)VDPolygon-Grade 算法的分級(jí)方法為前期數(shù)據(jù)處理過程中的手動(dòng)粗糙分級(jí)，未來將設(shè)計(jì)針對(duì)數(shù)據(jù)集的最優(yōu)分級(jí)方法，以保證各個(gè)子數(shù)據(jù)集內(nèi)的數(shù)據(jù)方差最小，數(shù)據(jù)集間方差最大，使候選集驗(yàn)證過程中產(chǎn)生最少冗余，進(jìn)一步提升算法效率；②主要驗(yàn)證了查詢面積、查詢邊界復(fù)雜程度對(duì)MVD-Polygon-Grade 算法的影響，未來將研究更多因素（如空間對(duì)象的密集程度）對(duì)該算法的影響，以拓展其應(yīng)用場(chǎng)景。