王中輝，閆浩文，楊艷春

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

基于方向和距離關系的復合空間查詢

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

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

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

四叉樹索引；方向關系；距離關系；復合空間查詢；算法

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

圖1 結合方向和距離關系的空間查詢

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

1 四叉樹索引

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

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

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

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

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

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

圖2 四叉樹索引

2 基于方向和距離關系的復合空間查詢算法

2.1 方向關系計算模型

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

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

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

2.2 算法描述

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

圖3 錐形模型

圖4 基于方向和距離關系的復合空間查詢

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

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

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

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

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

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

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

4)計算候選集中其MBR與OL1L2相交的空間對象和OL1L2之間的拓撲關系為：①空間對象與OL1L2相離，刪除該對象；②空間對象被OL1L2包含或與OL1L2相交，保留該對象。

3 實驗與討論

本文利用C#語言編程實現(xiàn)了提出的復合空間查詢算法，并使用不同幾何類型的空間對象(點、線、面)進行實驗。圖5～圖8是其中具有代表性的實驗結果。圖5、圖6的查詢對象為點，查詢條件分別是“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 實驗1

圖6 實驗2

圖7 實驗3

圖8 實驗4

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

圖9 查詢時間對比

分析上述實驗結果，可得出如下結論：

1)本文算法將方向和距離關系相結合進行空間查詢，有效地提高了空間查詢的準確性。

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

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

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

圖10 算法存在的缺陷

4 結束語

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

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

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

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

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

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

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

[7]董鵬,李津平,白予琦,等.基于改進四叉樹索引的矢量地圖疊加分析算法[J].計算機輔助設計與圖形學學報,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.

[責任編輯：劉文霞]

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ù)字制圖與國土信息應用工程國家測繪地理信息局重點實驗室開放研究基金資助項目(GCWD201210)；蘭州交通大學青年科學基金資助項目(2013001)；地理空間信息工程國家測繪地理信息局重點實驗室經(jīng)費資助項目(201313)

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

P208

：A

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