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

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

0 引 言

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

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

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

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

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

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

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

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

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

圖1 錐形模型Fig.1 Conical model

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

2 四叉樹(shù)索引

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

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

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

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

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

步驟2：插入空間對(duì)象

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

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

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

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

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

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

圖2 四叉樹(shù)索引Fig.2 Quad-tree index

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1：計(jì)算空間對(duì)象的MBR，建立四叉樹(shù)索引；

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

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

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

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

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

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

1）空間對(duì)象與OL1L2相離：刪除該對(duì)象；

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

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

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

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

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

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

表1 查詢性能對(duì)比Tab.1 Comparisons of spatial query performance

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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