基于方向和距離關(guān)系的復(fù)合空間查詢

王中輝，閆浩文，楊艷春

(1. 蘭州交通大學(xué) 測繪與地理信息學(xué)院，甘肅 蘭州 730070； 2. 蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

基于方向和距離關(guān)系的復(fù)合空間查詢

王中輝1，閆浩文1，楊艷春2

(1. 蘭州交通大學(xué) 測繪與地理信息學(xué)院，甘肅 蘭州 730070； 2. 蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

利用四叉樹索引，提出一種基于方向和距離關(guān)系的復(fù)合空間查詢算法。其基本思路是：計算給定的方向區(qū)域和距離范圍之間的交S,借助四叉樹索引快速查找其MBR(Minimum Bounding Rectangle)被S包含或與S相交的空間對象，構(gòu)成候選集，從候選集中刪除不符合給定方向和距離關(guān)系的空間對象，得到查詢結(jié)果。實(shí)驗(yàn)表明，算法具有較好的空間查詢性能。

四叉樹索引；方向關(guān)系；距離關(guān)系；復(fù)合空間查詢；算法

空間查詢是指從空間數(shù)據(jù)庫中檢索出滿足給定空間關(guān)系的空間實(shí)體，它是GIS的核心功能之一，也是GIS區(qū)別于其它信息系統(tǒng)的本質(zhì)特征，在航海、漁業(yè)、智能交通、環(huán)境監(jiān)測等領(lǐng)域有著廣泛的應(yīng)用[1-2]。目前，空間查詢的研究主要集中在方向或距離等單個空間關(guān)系上[3-6]。然而，在實(shí)際應(yīng)用中，往往需要將方向和距離關(guān)系相結(jié)合，才能對空間目標(biāo)進(jìn)行準(zhǔn)確查詢。例如在查詢圖1中位于居民地A的北面，距離小于50 m的地塊B1時，若基于方向關(guān)系查詢，則結(jié)果為B1，B4兩個地塊；若基于距離關(guān)系查詢，則結(jié)果為B1，B2，B33個地塊。顯然，在該情形下，只有將方向和距離關(guān)系相結(jié)合，地塊B1才會被準(zhǔn)確無誤地查詢出來。

圖1 結(jié)合方向和距離關(guān)系的空間查詢

本文利用四叉樹索引，提出一種基于方向和距離關(guān)系的復(fù)合空間查詢算法。目的是能夠在給定的方向和距離約束條件下，對點(diǎn)、線、面等空間對象進(jìn)行有效檢索，以提高空間查詢的整體性能。

1 四叉樹索引

空間索引是介于空間操作和空間對象之間的一種輔助性數(shù)據(jù)結(jié)構(gòu)，通過它的篩選，大量與特定操作無關(guān)的空間對象被排除，使空間操作能夠快速地訪問操作對象，從而極大地提高空間查詢的效率[7]。目前常用的空間索引主要有二叉樹索引、格網(wǎng)索引、R樹索引和四叉樹索引等。

與其它空間索引相比，四叉樹索引的優(yōu)點(diǎn)是結(jié)構(gòu)簡單、數(shù)據(jù)冗余低，常用于加速空間對象間拓?fù)潢P(guān)系的計算。其基本思想是：將已知范圍的空間劃分成4個相等的子空間，如果需要可以將每個或其中幾個子空間繼續(xù)劃分下去(樹的深度由用戶指定)，這樣就形成了一個基于四叉樹的空間劃分[7]。其具體構(gòu)建過程描述如下：

1)構(gòu)建空四叉樹。首先，計算空間對象的分布范圍從而確定樹的根節(jié)點(diǎn)矩形；然后，從根節(jié)點(diǎn)開始，將節(jié)點(diǎn)矩形平均劃分為4個小矩形，創(chuàng)建出4個子節(jié)點(diǎn)，并對這4個子節(jié)點(diǎn)遞歸執(zhí)行此過程，直至樹的深度達(dá)到給定的值。此時所構(gòu)建的四叉樹是一個空的滿四叉樹。

2)插入空間對象。從根節(jié)點(diǎn)開始，如果當(dāng)前節(jié)點(diǎn)包含空間對象的MBR，分兩種情況插入該對象：①當(dāng)前節(jié)點(diǎn)為葉節(jié)點(diǎn)：將空間對象插入到當(dāng)前節(jié)點(diǎn)中；②當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)或中間節(jié)點(diǎn)：判斷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否包含空間對象的MBR，如果包含，則把該子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，遞歸執(zhí)行過程①、②；如果都不包含(相交或相離)，則將空間對象插入到當(dāng)前節(jié)點(diǎn)中。

3)刪除空節(jié)點(diǎn)。由上述過程創(chuàng)建的四叉樹可能存在空節(jié)點(diǎn)，為節(jié)省存儲空間，需要對它們進(jìn)行刪除。即從根節(jié)點(diǎn)開始，逐節(jié)點(diǎn)進(jìn)行查找，如果當(dāng)前節(jié)點(diǎn)沒有子節(jié)點(diǎn)并且不含有空間對象，則刪除該節(jié)點(diǎn)；如果當(dāng)前節(jié)點(diǎn)包含子節(jié)點(diǎn)，則把子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)遞歸執(zhí)行此過程，直至索引樹中的所有節(jié)點(diǎn)都遍歷完畢。

如圖2所示，由于四叉樹索引的根節(jié)點(diǎn)和中間節(jié)點(diǎn)都能夠存儲空間對象，且各節(jié)點(diǎn)所存儲的空間對象不重復(fù)，因此它有效地降低了數(shù)據(jù)的冗余，具有較好的空間索引性能。為此，本文將選用四叉樹作為空間查詢的索引結(jié)構(gòu)。

圖2 四叉樹索引

2 基于方向和距離關(guān)系的復(fù)合空間查詢算法

2.1 方向關(guān)系計算模型

目前提出的方向關(guān)系計算模型主要有：矩形模型[8]、方向Voronoi圖模型[9]、方向關(guān)系統(tǒng)計模型[10]、方向關(guān)系矩陣模型[11]和錐形模型[12]。

矩形模型的優(yōu)點(diǎn)是簡單、直觀，但該模型對方向關(guān)系的描述太過近似，因此很少應(yīng)用于空間查詢；方向Voronoi圖模型和方向關(guān)系統(tǒng)計模型對方向的描述雖然精確但計算復(fù)雜，不適合于高效率的空間查詢；方向關(guān)系矩陣模型因受其方向區(qū)域劃分方式的限制，只能進(jìn)行八方向的空間查詢，無法在實(shí)際中得到廣泛應(yīng)用。

錐形模型以參考對象的幾何中心為起點(diǎn)，將空間劃分為幾個錐形方向區(qū)域，并通過判斷目標(biāo)對象與各方向區(qū)域之間的“交”是否為空，來描述空間方向。如圖3所示，目標(biāo)對象B與參考對象A的NE區(qū)域的“交”為非空，故B相對于A的空間方向關(guān)系為：Dir(A,B)=NE。與其它方向關(guān)系計算模型相比，錐形模型的優(yōu)點(diǎn)是計算簡單、實(shí)現(xiàn)容易，并且能夠根據(jù)空間查詢的不同需求，將空間劃分為四方向、八方向、十六方向等錐形區(qū)域。為此，本文擬采用錐形模型作為空間查詢的方向關(guān)系計算模型。

2.2 算法描述

圖4中，A表示參考對象，錐形區(qū)域表示給定的方向區(qū)域，圓形區(qū)域表示給定的距離范圍。本文算法的基本思路是：首先，計算給定的方向區(qū)域和距離范圍之間的交，圖4中的扇形區(qū)域OL1L2；然后，借助四叉樹索引查找被OL1L2包含或與OL1L2相交的空間對象，得到查詢結(jié)果，如圖4中的陰影多邊形。

圖3 錐形模型

圖4 基于方向和距離關(guān)系的復(fù)合空間查詢

四叉樹索引是用MBR近似表示空間對象，而MBR在許多情況下并不能正確代表空間對象自身與其它圖形目標(biāo)之間的拓?fù)潢P(guān)系。如圖4所示，雖然空間對象B的MBR(虛線矩形)與扇形區(qū)域OL1L2相交，但B自身和OL1L2并不相交。為此，本文將空間查詢分為以下兩個過程：

1)過濾。利用四叉樹索引快速查找其MBR被OL1L2包含或與OL1L2相交的空間對象，構(gòu)成候選集。

2)提煉。從候選集中刪除不符合給定方向和距離關(guān)系的空間對象，得到查詢結(jié)果。

下面結(jié)合圖4對算法的具體執(zhí)行過程進(jìn)行詳細(xì)的描述。算法用到四叉樹索引的一個重要特性，即四叉樹索引的某個節(jié)點(diǎn)所表示的空間區(qū)域總是包含在其父節(jié)點(diǎn)所表示的空間區(qū)域中。

1)計算空間對象的MBR，建立四叉樹索引。

2)計算給定的方向區(qū)域和距離范圍之間的交OL1L2。

3)從四叉樹的根節(jié)點(diǎn)開始，判斷當(dāng)前節(jié)點(diǎn)與扇形區(qū)域OL1L2之間的拓?fù)潢P(guān)系為：①當(dāng)前節(jié)點(diǎn)與OL1L2相離，直接返回上一層；②當(dāng)前節(jié)點(diǎn)包含在OL1L2內(nèi)，將該節(jié)點(diǎn)(包括其子節(jié)點(diǎn))存儲的所有空間對象加入候選集，返回上一層；③當(dāng)前節(jié)點(diǎn)與OL1L2相交，如果該節(jié)點(diǎn)存儲了空間對象，判斷每個空間對象的MBR與OL1L2的拓?fù)潢P(guān)系，如果相交或被OL1L2包含，則將該空間對象加入候選集；如果該節(jié)點(diǎn)還包含有子節(jié)點(diǎn)，則把子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)遞歸執(zhí)行步驟3)，否則，返回上一層。

4)計算候選集中其MBR與OL1L2相交的空間對象和OL1L2之間的拓?fù)潢P(guān)系為：①空間對象與OL1L2相離，刪除該對象；②空間對象被OL1L2包含或與OL1L2相交，保留該對象。

3 實(shí)驗(yàn)與討論

本文利用C#語言編程實(shí)現(xiàn)了提出的復(fù)合空間查詢算法，并使用不同幾何類型的空間對象(點(diǎn)、線、面)進(jìn)行實(shí)驗(yàn)。圖5～圖8是其中具有代表性的實(shí)驗(yàn)結(jié)果。圖5、圖6的查詢對象為點(diǎn)，查詢條件分別是“Direction = SE，10 d < Distance < 20 d”和“Direction = SW，Distance < 10d或Distance > 20 d”；圖7的查詢對象為線，查詢條件是“Direction = NE，Distance < 20 d”；圖8的查詢對象為面，查詢條件是“Direction = W，Distance > 10 d”。其中，符號d表示地圖距離單位。

圖5 實(shí)驗(yàn)1

圖6 實(shí)驗(yàn)2

圖7 實(shí)驗(yàn)3

圖8 實(shí)驗(yàn)4

為檢驗(yàn)算法的查詢性能，本文對利用四叉樹索引(樹的深度為4)和不利用四叉樹索引的兩種復(fù)合空間查詢進(jìn)行了對比測試。實(shí)驗(yàn)環(huán)境為Intel Core2 處理器(主頻為2 GHz)，內(nèi)存為2 GB，測試數(shù)據(jù)采用比例尺為1∶400萬的矢量線目標(biāo)數(shù)據(jù)(線目標(biāo)的個數(shù)為11 333)。查詢條件為“Directions = {N, NE, E, SE, S, SW, W, NW}，Distance < 20 d”。圖9給出了兩種方法的查詢時間對比結(jié)果。

圖9 查詢時間對比

分析上述實(shí)驗(yàn)結(jié)果，可得出如下結(jié)論：

1)本文算法將方向和距離關(guān)系相結(jié)合進(jìn)行空間查詢，有效地提高了空間查詢的準(zhǔn)確性。

2)本文算法的通用性較好，能夠處理不同幾何類型的空間對象(點(diǎn)、線、面)。

3)本文算法采用四叉樹作為空間索引結(jié)構(gòu)，較好地提高了空間查詢的效率。

4)本文算法的局限性在于：由于錐形模型將參考目標(biāo)抽象為一個點(diǎn)，忽略了參考目標(biāo)的形狀和大小對方向關(guān)系的影響，當(dāng)兩目標(biāo)之間的距離相對于自身大小較近時，容易出現(xiàn)查詢上的偏差。如圖10所示，在查詢參考對象A以東(E)一定距離范圍內(nèi)的空間對象時，由于錐形模型自身的缺陷，使得空間對象B被漏查。

圖10 算法存在的缺陷

4 結(jié)束語

本文利用四叉樹索引，通過計算給定的方向區(qū)域和距離范圍之間的交，實(shí)現(xiàn)了基于方向和距離關(guān)系的復(fù)合空間查詢。實(shí)驗(yàn)表明該算法具有較好的空間查詢性能。但由于錐形模型自身存在的缺陷，導(dǎo)致算法在某些情況下出現(xiàn)查詢偏差。進(jìn)一步的研究工作是對錐形模型進(jìn)行改進(jìn)，以完善復(fù)合空間查詢的性能。

[1]陳曉斌, 葛文, 余慧明, 等. 基于網(wǎng)格的空間數(shù)據(jù)分布式查詢技術(shù)研究[J]. 測繪工程, 2012,21(6):16-21.

[2]肖予欽, 張巨, 景寧, 等. 基于R樹的方向關(guān)系查詢處理[J]. 軟件學(xué)報, 2004,15(1):103-111.

[3]夏宇,朱欣焰,蘇科華.基于錐形模型的空間方向查詢研究[J].地理空間信息,2007,5(3):65-67.

[4]付迎春, 袁修孝, 聶啟祥. 擴(kuò)展的錐形方向關(guān)系查詢處理方法[J]. 計算機(jī)工程, 2008,34(15):36-38.

[5]張澤寶,張健沛,李若愚. R樹的方向查詢精過濾方法[J].哈爾濱工程大學(xué)學(xué)報,2010,31(11):1490-1495.

[6]李進(jìn),余建橋.空間對象的反最近鄰查詢處理技術(shù)研究[J].計算機(jī)工程與應(yīng)用,2011,47(33):146-148.

[7]董鵬,李津平,白予琦,等.基于改進(jìn)四叉樹索引的矢量地圖疊加分析算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2004,16(4):530-534.

[8]PAPADIAS D, EGENHOFER M. Algorithms for hierarchical reasoning[J]. GeoInformatica,1994,1(3): 251-273.

[9]YAN H, CHU Y, LI Z, et al. A quantitative description model for direction relations based on direction groups[J]. Geoinformatica, 2006, 10(2):177-196.

[10]DENG M, LI Z. A statistical model for directional relations between spatial objects[J]. Geoinformatica, 2008, 12(2):193-217.

[11]GOYAL R K. Similarity assessment for cardinal directions between extended spatial objects[D]. PHD Thesis, The University of Maine, 2000.

[12]PEUQUET D, ZHAN C X. An algorithm to determine the directional relation between arbitrarily-shaped polygons in the plane[J]. Pattern Recognition, 1987, 20(1): 65-74.

[責(zé)任編輯：劉文霞]

Compound spatial query based on direction and distance relations

WANG Zhong-hui1, YAN Hao-wen1, YANG Yan-chun2

(1. School of Geomatics, Lanzhou Jiaotong University, Lanzhou 730070, China; 2. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

An algorithm for compound spatial query based on direction and distance relations is proposed by using quad-tree index. Its basic idea is: first, computing the intersection S of the given direction area and distance range; then, using quad-tree index to search quickly the objects whose MBR (Minimum Bounding Rectangle) contained by S or intersecting with S to construct the candidate set; finally, getting the result by removing the objects not meeting the given direction and distance relations in the candidate set. The experiments show that the algorithm has good performance.

quad-tree index; direction relations; distance relations; compound spatial query; algorithm

2013-09-09

國家科技支撐計劃資助項目(2013BAB05B01)；數(shù)字制圖與國土信息應(yīng)用工程國家測繪地理信息局重點(diǎn)實(shí)驗(yàn)室開放研究基金資助項目(GCWD201210)；蘭州交通大學(xué)青年科學(xué)基金資助項目(2013001)；地理空間信息工程國家測繪地理信息局重點(diǎn)實(shí)驗(yàn)室經(jīng)費(fèi)資助項目(201313)

王中輝(1978-)，男，講師，博士研究生.

P208

：A

：1006-7949(2014)11-0007-04