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

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

0 引 言

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

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

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

1 空間方向關系計算模型

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

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

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

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

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

圖1 錐形模型Fig.1 Conical model

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

2 四叉樹索引

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

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

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

步驟1：構建空間四叉樹

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

步驟2：插入空間對象

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

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

2）當前節(jié)點為根節(jié)點或中間節(jié)點：判斷當前節(jié)點的子節(jié)點是否包含空間對象的MBR，如果包含，則把該子節(jié)點作為當前節(jié)點，遞歸執(zhí)行過程1）、2）；如果都不包含（相交或相離），則將空間對象插入到當前節(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 四叉樹索引Fig.2 Quad-tree index

3 基于方向關系的空間查詢算法

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

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

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

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

下面結合圖3詳細介紹算法的具體步驟。

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

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

步驟3：判斷當前節(jié)點N與錐形方向區(qū)域Di的拓撲關系：

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

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

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

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

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

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

圖4 結合方向和距離關系的空間查詢Fig.4 Spatial query by combined with direction and distance relations

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

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

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

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

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

步驟3：從四叉樹的根節(jié)點開始，判斷當前節(jié)點與扇形區(qū)域OL1L2之間的拓撲關系：

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

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

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

步驟4：計算候選集中其MBR與OL1L2相交的空間對象和OL1L2之間的拓撲關系：

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

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

5 實驗與討論

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

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

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

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

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

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

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

2）算法將方向和距離關系相結合進行空間查詢，有效地提高了空間查詢的準確性；

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

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

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

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

6 結束語

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