方向關(guān)系在空間查詢中的應(yīng)用研究

王中輝，孫 立，祿小敏，徐智邦

（1. 蘭州交通大學(xué) 測繪與地理信息學(xué)院，甘肅 蘭州 730070；2. 甘肅省地理國情監(jiān)測工程實驗室，甘肅 蘭州 730070）

0 引 言

空間方向關(guān)系是人們描述、表達(dá)地理空間必須要面對和研究的基本空間關(guān)系之一。空間方向關(guān)系作為空間查詢的重要選取條件，在空間數(shù)據(jù)挖掘和地理信息系統(tǒng)等許多空間信息科學(xué)領(lǐng)域得到了廣泛的應(yīng)用[1-5]。

目前，學(xué)者們對基于拓?fù)洹⒕嚯x關(guān)系的空間查詢研究已經(jīng)比較成熟；而對基于方向關(guān)系的空間查詢研究卻相對滯后[2]。文獻[1]利用矩形模型和R樹索引實現(xiàn)了基于方向關(guān)系的空間查詢，但由于矩形模型自身存在的缺陷，導(dǎo)致查詢結(jié)果在許多情況下出現(xiàn)錯誤；文獻[2-3]利用方向關(guān)系矩陣模型和R樹索引研究了基于方向關(guān)系的空間查詢，但該算法只能處理八方向的空間查詢；文獻[4]借助平面掃描技術(shù)提出了一種高效的基于方向關(guān)系的空間查詢算法，但該算法的查詢對象僅限于互不相交的矩形。

鑒于此，本文對方向關(guān)系在空間查詢中的應(yīng)用進行了研究。在分析和比較現(xiàn)有空間方向關(guān)系計算模型及空間索引的基礎(chǔ)上，利用錐形模型和四叉樹索引，提出了一種基于方向關(guān)系的空間查詢算法；并進一步結(jié)合空間距離關(guān)系，實現(xiàn)了基于方向和距離關(guān)系的復(fù)合空間查詢，有效地提高了空間查詢的性能。

1 空間方向關(guān)系計算模型

現(xiàn)有的空間方向關(guān)系計算模型主要包括：錐形模型、矩形模型、方向關(guān)系矩陣模型、方向Voronoi圖模型和方向關(guān)系統(tǒng)計模型。

矩形模型[6]用兩目標(biāo)的MBR之間的方向關(guān)系來確定兩目標(biāo)之間的方向關(guān)系，但由于MBR之間的關(guān)系在許多情況下并不能精確代表目標(biāo)之間的真實關(guān)系，因此該模型是一個近似描述模型，在進行空間查詢時容易出現(xiàn)錯誤的查詢結(jié)果，目前已很少使用。

方向Voronoi圖模型[7]借助目標(biāo)間指向線法線的Voronoi 圖得到目標(biāo)間的方向關(guān)系；方向關(guān)系統(tǒng)計模型[8]通過統(tǒng)計目標(biāo)間可視點之間的方位角，對目標(biāo)間的方向關(guān)系進行描述。這兩個模型的優(yōu)點是對方向關(guān)系的描述較其他模型要精確，但它們的計算都過于復(fù)雜，難以滿足空間查詢的高效性要求。

方向關(guān)系矩陣模型[9]以參考目標(biāo)的MBR為中心將空間劃分為固定的八個矩形方向區(qū)域，并用源目標(biāo)與各方向區(qū)域之間交的結(jié)果作為元素構(gòu)成方向關(guān)系矩陣來表達(dá)空間方向。該模型的優(yōu)點是計算簡單、實現(xiàn)容易，但它只能處理八方向的空間查詢，無法滿足實際應(yīng)用的需求。

錐形模型[10]的基本思想是：以參考目標(biāo)的幾何中心為起點，將空間劃分為若干個錐形方向區(qū)域，并通過源目標(biāo)與各方向區(qū)域之間的交來描述空間方向。圖1所示為八方向錐形模型，圖中源目標(biāo)B相對于參考目標(biāo)A的方向關(guān)系為東（E）。

圖1 錐形模型Fig.1 Conical model

由于錐形模型是針對目標(biāo)本身來計算方向關(guān)系的，因此在準(zhǔn)確性上要優(yōu)于矩形模型；此外，錐形模型結(jié)構(gòu)簡單，在計算效率上要高于方向Voronoi圖模型和方向關(guān)系統(tǒng)計模型，并且能夠根據(jù)實際應(yīng)用的不同需求，將空間劃分為四方向、八方向、十六方向等錐形區(qū)域。為此，本文采用錐形模型實現(xiàn)基于方向關(guān)系的空間查詢。

2 四叉樹索引

在利用錐形模型進行基于方向關(guān)系的空間查詢時，需要依次判斷各空間對象與給定錐形方向區(qū)域之間的拓?fù)潢P(guān)系。因此，當(dāng)空間對象的數(shù)據(jù)量不斷增加時，其查詢效率將會迅速下降，而解決該問題的關(guān)鍵是為空間查詢建立合適的空間索引[11]。

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

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

步驟1：構(gòu)建空間四叉樹

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

步驟2：插入空間對象

從根節(jié)點開始，如果當(dāng)前節(jié)點包含空間對象的MBR，分2種情況插入該對象：

1）當(dāng)前節(jié)點為葉節(jié)點：將空間對象插入到當(dāng)前節(jié)點中；

2）當(dāng)前節(jié)點為根節(jié)點或中間節(jié)點：判斷當(dāng)前節(jié)點的子節(jié)點是否包含空間對象的MBR，如果包含，則把該子節(jié)點作為當(dāng)前節(jié)點，遞歸執(zhí)行過程1）、2）；如果都不包含（相交或相離），則將空間對象插入到當(dāng)前節(jié)點中。

步驟3：刪除空節(jié)點

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

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

圖2 四叉樹索引Fig.2 Quad-tree index

3 基于方向關(guān)系的空間查詢算法

在四叉樹索引中，空間對象是用其MBR來表示，但是在進行基于方向關(guān)系的空間查詢時，空間對象的MBR與方向區(qū)域之間的拓?fù)潢P(guān)系在許多情況下并不能正確代表空間對象自身與方向區(qū)域之間的拓?fù)潢P(guān)系。如圖3所示，雖然空間對象P的MBR與給定的錐形方向區(qū)域Di相交，但P自身和Di并不相交。因此，本文將空間查詢分為以下2個過程。

圖3 基于方向關(guān)系的空間查詢Fig.3 Spatial query based on direction relations

1）過濾：借助錐形模型和四叉樹索引快速查找其MBR符合給定方向關(guān)系的空間對象，構(gòu)成候選集S1；

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

下面結(jié)合圖3詳細(xì)介紹算法的具體步驟。

步驟1：計算各空間對象的MBR，并建立它們的四叉樹空間索引，詳細(xì)算法參見文獻[11]；

步驟2：以參考目標(biāo)R的幾何中心O為起點，構(gòu)建給定的錐形方向區(qū)域Di，并將四叉樹的根節(jié)點作為當(dāng)前節(jié)點N；

步驟3：判斷當(dāng)前節(jié)點N與錐形方向區(qū)域Di的拓?fù)潢P(guān)系：

①當(dāng)前節(jié)點N與錐形方向區(qū)域Di相離：直接返回上一層；

②當(dāng)前節(jié)點N包含在錐形方向區(qū)域Di內(nèi)：將節(jié)點N（包括其子節(jié)點）存儲的所有空間對象加入候選集S1，返回上一層；

③當(dāng)前節(jié)點N與錐形方向區(qū)域Di相交：如果節(jié)點N存儲了空間對象，判斷節(jié)點N中每個空間對象的MBR與Di的拓?fù)潢P(guān)系，如果相交或被Di包含，則將該空間對象加入候選集S1；如果節(jié)點N還包含有子節(jié)點，則依次把每個子節(jié)點作為當(dāng)前節(jié)點N，遞歸執(zhí)行步驟3，否則，返回上一層。

步驟4：從候選集S1中找出其MBR與錐形方向區(qū)域Di相交的所有空間對象，并判斷其中的每個空間對象與Di的拓?fù)潢P(guān)系，若與Di相交或被Di包含，則保留該空間對象；否則，刪除該空間對象。從而得到結(jié)果集S2，如圖3中的陰影多邊形。

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

在實際應(yīng)用中，往往需要將方向和距離關(guān)系相結(jié)合，才能對空間目標(biāo)進行準(zhǔn)確、快速地查詢。如在查詢圖4中“位于居民地A的北面并且距離小于50 m”的地塊B1時，若基于方向關(guān)系查詢，則結(jié)果為B1、B4兩個地塊；若基于距離關(guān)系查詢，則結(jié)果為B1、B2、B3三個地塊。顯然，在該情形下，只有將方向和距離關(guān)系相結(jié)合，地塊B1才會被準(zhǔn)確、高效地查詢出來。不失一般性，下面以“在某方向并且小于指定距離”為查詢條件對算法進行說明。

圖4 結(jié)合方向和距離關(guān)系的空間查詢Fig.4 Spatial query by combined with direction and distance relations

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

圖5 基于方向和距離關(guān)系的復(fù)合空間查詢Fig.5 Compound spatial query based on direction and distance relations

下面結(jié)合圖5對算法的執(zhí)行過程進行詳細(xì)的描述。

步驟1：計算空間對象的MBR，建立四叉樹索引；

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

步驟3：從四叉樹的根節(jié)點開始，判斷當(dāng)前節(jié)點與扇形區(qū)域OL1L2之間的拓?fù)潢P(guān)系：

1）當(dāng)前節(jié)點與OL1L2相離：直接返回上一層；

2）當(dāng)前節(jié)點包含在OL1L2內(nèi)：將該節(jié)點（包括其子節(jié)點）存儲的所有空間對象加入候選集，返回上一層；

3）當(dāng)前節(jié)點與OL1L2相交：如果該節(jié)點存儲了空間對象，判斷每個空間對象的MBR與OL1L2的拓?fù)潢P(guān)系，如果相交或被OL1L2包含，則將該空間對象加入候選集；如果該節(jié)點還包含有子節(jié)點，則把子節(jié)點作為當(dāng)前節(jié)點遞歸執(zhí)行步驟3，否則，返回上一層。

步驟4：計算候選集中其MBR與OL1L2相交的空間對象和OL1L2之間的拓?fù)潢P(guān)系：

1）空間對象與OL1L2相離：刪除該對象；

2）空間對象被OL1L2包含或與OL1L2相交：保留該對象。

5 實驗與討論

為檢驗上述算法的查詢性能，本文利用C#語言對算法進行了編程實現(xiàn)，并使用不同幾何類型的空間對象（點、線、面）進行了實驗。圖6、圖7是其中具有代表性的兩組實驗結(jié)果，在圖7中，d表示地圖距離單位。

圖6 基于方向關(guān)系的空間查詢實驗Fig.6 Experiments of spatial query based on direction relations

圖7 基于方向和距離關(guān)系的復(fù)合空間查詢實驗Fig.7 Experiments of compound spatial query based on direction and distance relations

為檢驗算法的查詢性能，本文對利用四叉樹索引（樹的深度為4）和不利用四叉樹索引的兩種復(fù)合空間查詢進行了對比測試。實驗環(huán)境為Intel Core2處理器（主頻為2GHz），內(nèi)存為2GB，測試數(shù)據(jù)采用比例尺為1:4000000的矢量線目標(biāo)數(shù)據(jù)（線目標(biāo)的個數(shù)為11 333）。查詢條件為“Direction={N,NE,E,SE,S,SW,W,NW}and Distance＜20 d”。表1給出了兩種方法查詢目標(biāo)對象時所需的比較次數(shù)以及執(zhí)行時間，列（%）分別表示利用四叉樹索引的比較次數(shù)、執(zhí)行時間相對于不利用四叉樹索引的比較次數(shù)、執(zhí)行時間的百分比。

表1 查詢性能對比Tab.1 Comparisons of spatial query performance

分析上述實驗結(jié)果，可得出以下結(jié)論：

1）算法能夠?qū)崿F(xiàn)基于四方向、八方向和十六方向的空間查詢，較好地滿足了實際應(yīng)用的需求；

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

3）算法能夠處理不同幾何類型的空間數(shù)據(jù)（點、線、面），具有較好的通用性；

4）算法采用四叉樹作為空間索引結(jié)構(gòu)，顯著地提高了空間查詢的效率；

5）算法的局限性在于，當(dāng)兩目標(biāo)之間的距離相對于自身大小很近時，容易出現(xiàn)查詢上的偏差。如圖8所示，在利用錐形模型查詢參考目標(biāo)A以東（E）的空間對象時，與A鄰近的目標(biāo)B被漏查。

圖8 錐形模型存在的缺陷Fig.8 Defects of conical model

6 結(jié)束語

本文針對方向關(guān)系在空間查詢中的應(yīng)用進行了研究，在分析比較現(xiàn)有空間方向關(guān)系計算模型及空間索引結(jié)構(gòu)的基礎(chǔ)上，選用錐形模型和四叉樹索引提出了一種基于方向關(guān)系的空間查詢算法，進而通過計算給定方向區(qū)域和距離范圍之間的交，實現(xiàn)了基于方向和距離關(guān)系的復(fù)合空間查詢。實驗表明，提出的算法能夠?qū)Σ煌瑤缀晤愋偷目臻g數(shù)據(jù)進行準(zhǔn)確、高效的查詢，較好地滿足了實際應(yīng)用的需求。但由于錐形模型自身存在的不足，導(dǎo)致查詢結(jié)果在某些情況下出現(xiàn)偏差，該問題的解決有賴于空間方向關(guān)系計算模型的進一步改進與完善。