肖 怡，李佳田，張文靖，劉 鵬，王 瑜，張思佳

（昆明理工大學 國土資源工程學院，云南 昆明 650093）

0 引 言

空間目標與它生成的Voronoi區(qū)域距離最近，如果兩個空間目標具有共同Voronoi邊界，那么這兩個空間目標之間存在著自然鄰近空間關系[1]。自然鄰近在自然地表內(nèi)插[2-3]、空間鄰近查詢[4]、制圖綜合[5-6]以及模式分類[7-8]等領域是一個十分重要的研究內(nèi)容。然而，現(xiàn)有的空間數(shù)據(jù)庫并不支持自然鄰近空間關系查詢，制約著空間數(shù)據(jù)庫技術在GIS中的應用。

Voronoi圖將空間鄰近關系隱含于其中。Long等基于Voronoi的空間關系-V9I的基礎上進一步分析了A，B兩個空間目標之間的空間關系，其中用3×3布爾矩陣表示了A，B自然鄰近的情況[9-10]。Xie等提出了不確定的Voronoi圖(或UV圖)，它將數(shù)據(jù)空間分為不相交的“UV分區(qū)”。每個UV分區(qū)P與目標集合S相關聯(lián)，使得位于P中的任何點q都有集合S作為它的最近鄰居[11]。Trefftz 等用空間目標的k階Voronoi圖，進而進行鄰近查詢[12-13]。但是由于至今全要素的Voronoi圖的生成方法并不成熟，研究學者紛紛將目光轉向Voronoi的對偶Delaunay三角網(wǎng)，Gold等提出了將三角形中的三邊根據(jù)鄰近關系以及邊的逆時針方向來分類進而形成二叉樹序列來判斷自然鄰近空間關系[14-15]。但二叉樹不是多路平衡樹且更新不便。Jones等使用了規(guī)則格網(wǎng)索引對三角形做了預處理，通過三角形的鄰近關系來確定影響三角形的集合，這種方法被稱為簡單格網(wǎng)索引方法(Simple Grid Index，SGI)[16]。但是這種方法會存儲大量的三角形，占用較多的磁盤空間并且不支持更新。

本文的主要工作是將離散面目標映射到約束Delaunay三角網(wǎng)中，提出Unions Delaunay結構來描述離散面目標之間的鄰近區(qū)域，進而構建R-tree Gridfile空間索引結構，R-tree Gridfile建立了空間選擇范圍和分離的空間目標之間的相互聯(lián)系以此來克服“交”運算不能運用于自然鄰近關系查詢這一問題。R-tree Gridfile是通過R-tree與Gridfile相結合的索引結構來實現(xiàn)規(guī)則空間剖分，對比實驗結果表明該空間索引結構通過葉結點部分重構來代替整體更新的方法能夠有效地支持離散面目標集合地鄰近查詢。

1 Unions Delaunay結構

Unions Delaunay結構是在Delaunay三角剖分的基礎上，將空間目標剖分成三角形,然后根據(jù)三角形邊的來源不同重分類，將表示相同鄰近空間關系的三角形合并成一個Union，形成空間目標集合和自然鄰近空間關系區(qū)域相互結合的一種空間剖分結構-Unions Delaunay。用其最小外接矩形(Minimal Bounding Rectangle，MBR)來近似區(qū)域，提高了磁盤的空間利用率，減少了索引時間。

三角網(wǎng)中三角形的分類是基于三角形的三條邊來源于幾個空間目標，以此來將三角形分為3種不同類型的三角形，Union構造過程如圖1所示。

圖1 Union構建過程Fig.1 Building process for Union

圖1 中的β型三角形指這類三角形中的三條邊分別來源于兩個不同的空間目標，α型三角形指的是三條邊來源于同一個空間目標的三角形，這類三角形中如果其重心在其內(nèi)部，則為δ型三角形，δ型三角形是α型三角形中的一種。

2 R-tree Gridefile空間索引

空間索引在空間數(shù)據(jù)庫中是一種有效的檢索手段，其基本思想是對近似(approximation)的使用，根本目的是減少讀盤。R-tree采用了B樹分割空間的思想[17-18]，在更新索引結構時能夠以局部代替整體，僅涉及到子結點的合并與分割。而Gridfile采用多屬性索引技術來分割嵌入的n維空間，實現(xiàn)二次磁盤訪問[19]。通過運用Unions Delaunay結構與R-tree Gridefile相結合，首先提取空間目標的最小完備鄰近目標的候選集合，其次建立空間目標與空間選擇的關系，從而使得“交”運算同樣能夠用于自然鄰近空間關系計算中。

2.1 R-tree Gridfile的結構

在Unions Delaunay結構中存儲了三角形的空間鄰近關系，但是并沒有存儲三角形，所以該結構并不具有實時更新的特征。故在二維歐式空間中采用層次空間剖分方法，用低層面片的重構來代替整體結構的更新。R-tree Gridfile包括R-tree和Gridfile兩個基本結構，R-tree 構成二維歐式空間中有界區(qū)域的層次剖分，樹的根結點代表S，R-tree 采用了MBR的方法，對葉子結點所指向的目標空間用其MBR框起來，越是接近S，框所代表的空間范圍就越大，以此來對空間進行規(guī)則剖分。在R樹中每個葉子結點代表1個最小剖分單元(Minimum split unit，MSU)，存放其MBR并指向一個Gridfile結構，葉子結點的結構組成包括其MSU所代表的空間范圍以及對應的Gridfile的指針，表示為(MBRi，Gridfile_ptri）。每個結點代表一個剖分單元，可能包含多個MSU，結點結構由自身代表的多個MSU的“并”集以及其包含的葉子結點的指針構成，表示為(MBRi，＜child_ptrim，child_ptrim+1，…，child_ptriM＞)，其中MBR為樹的結點所包含的空間范圍。除根結點外，每個結點的項數(shù)介于最小項數(shù)m和最大項數(shù)M之間，且1≤m≤M/2，下限保證對磁盤空間的有效利用，上限保證每個結點對應一個磁盤頁。樹形結構及其相對應的空間分布圖如圖2、圖3所示。在圖3中R9區(qū)域中存在數(shù)據(jù)集，我們用MBR框住該區(qū)域，其他區(qū)域類似，圖中R3、R4、R5與R1之間的距離相比R2較近，這由公式(2)來說明，所以將其放入R1的MBR中。R-tree代表了一種規(guī)則的、自下而上的空間剖分結構，是空間分割的典型體現(xiàn)。R-tree用葉子結點來代表一個MSU，并且借助其MBR來代表所指向的Gridfile，使得在數(shù)據(jù)庫中的空間索引查詢變成了對空間目標所代表的外接矩形進行分析，空間索引只需要訪問少量的結點，即可完成對空間目標的快速定位以及分析工作。R-tree Gridfile空間索引具有實時更新的特征。在格網(wǎng)文件單元中包含了空間目標在格網(wǎng)文件中的空間索引信息，由于將整個離散面進行規(guī)則格網(wǎng)剖分，所以在這里的空間索引信息即為空間目標在格網(wǎng)中的屬性信息形如(xi，yi，locasi1，locasi2，backet_fid)，如圖4，圖5所示，其中(xi，yi)表示空間目標在格網(wǎng)中的位置，在格網(wǎng)索引中每一個格網(wǎng)都被稱為一個桶(backet)，將落入該格網(wǎng)內(nèi)的空間目標放入到該格網(wǎng)對應的桶中，從而在空間索引時只對含有空間目標的桶索引。(locasi1，locasi2，backet_fid)表示格網(wǎng)單元記錄的桶的首尾地址以及桶的編號，桶中存儲的二元組表示了在Union中有鄰近空間關系的目標的標號fid。

圖3 R樹的空間分布圖Fig.3 Spatial distribution map of R-tree

圖4 R-tree Gridfile的基本結構Fig.4 The basic structure of R-tree Gridfile

定義1(空間占用)：在二維歐式空間中，空間目標a(xj,yj)，b(xj,yj)之間的距離常用歐式距離(公式（1）)來表示，但是這種方法不能夠很好地表示a、b之間的空間關系，本文采用空間占用來表示a、b之間的距離?？臻g占用即a、b的MBR的外接圓之間的關系，在表示a、b之間的空間關系上具有優(yōu)越的性能，所以本文計算目標之間的距離采用公式（2）的方法?？臻g占用的計算決定著在R-tree的子結點項數(shù)達到M時，即滿足分裂條件后，對空間目標所代表的MBR的處理方法。在二維歐式空間中，兩個空間目標a,b之間的空間占用關系見公式（2）。

dis(a,b)的值越小，表示兩個空間目標之間的距離越近，反之，則表示距離越遠。如果非根結點所包含的項數(shù)達到M項，那么該結點即達到了分裂的條件，首先計算這M項中dis(a、b)最大的值，找到(a、b)兩個空間目標，生成各自的MBR，然后再判斷剩余的M-2項的空間實體Q={q1，q2…，qM-2}與a、b之間的空間占用關系，如果dis(qi，a)≤dis(qi，b)，那么將qi的MBR與a所代表的空間的MBR構建一個新的MBR。反之將qi的MBR與b所代表的空間的MBR構建一個新的MBR。公式中a,b表示兩個空間中的實體，area代表了求取其MBR外接圓的面積函數(shù)。

R-tree Gridfile是通過R樹與Gridfile相結合的索引結構來實現(xiàn)規(guī)則空間剖分，這種混合空間索引機制能夠將大量的索引項有序地組織到索引結構中，對R-tree Gridfile空間索引結構中的葉子結點指向的空間目標采用Gridfile索引方式進行查詢。R-tree Gridfile索引文件的物理結構包含4個基本要素如圖5所示。

圖5 索引文件結構Fig.5 Index fi le structure

圖5 中的start代表了該格網(wǎng)文件對應的桶的首地址，next start表示下一個桶的首地址，fid表示桶在格網(wǎng)文件中的索引號，由公式(3)求得，xg，yg表示所求空間目標P所在桶的地理坐標。由公式(4)求得。位置關系如圖6所示。

式中，W表示格網(wǎng)的寬度，H表示格網(wǎng)的高度，|result|表示對所得到的結果result取整數(shù)，xp，yp代表了空間目標在格網(wǎng)中的坐標，即像素坐標，這里需要將P所在的像素坐標轉換成地理坐標，使之攜帶地理信息，同時使得P在格網(wǎng)中的行列號與具體的地理坐標建立了對應關系，并使得目標索引得以建立。Δx，Δy指明了格網(wǎng)的規(guī)則剖分尺度，其值的大小是影響格網(wǎng)空間索引效率的一個重要因素，格網(wǎng)單元太大時會導致每個格網(wǎng)單元中包含較多的空間目標，格網(wǎng)單元太小則會造成多個網(wǎng)格單元會索引到同一個空間目標，都會造成空間索引時間的增加，影響索引效率。因此格網(wǎng)單元大小的選擇需要根據(jù)地理空間目標的窗口數(shù)來多次測試格網(wǎng)單元的劃分，以此取得較好的索引效率。

圖6 位置關系圖Fig.6 Position relationship diagram

2.2 R-tree Gridfile構建算法

下面介紹基于 Unions Delaunay三角網(wǎng)創(chuàng)建 R-tree Gridfile空間索引結構的算法，其構建流程圖如圖7所示。由程序流程圖可以看出在索引結構的構建過程中，輸入的是三角形集合Unions Delaunay。輸出的則是R-tree Gridfile空間索引結構。在該過程中主要涉及到幾個基本部分，格網(wǎng)單元的劃分被首先確定，其前提是經(jīng)過對空間目標窗口數(shù)的多次比較得到性能較優(yōu)的劃分，其重要的步驟為掃描Union以及寫入索引文件，即圖7中的兩條分支，在左分支，即掃描Union的過程中獲取Unionn以及其MBR在格網(wǎng)中的相關信息，同時創(chuàng)建二元組，形如＜fid1，fid2＞，表示在Unionn中有鄰近空間關系的目標fid；在寫入索引文件的過程中，核心過程為得到以及更新格網(wǎng)單元中記錄的形如(xi，yi，locasi1，locasi2，backet_fid)的信息。

圖7 Gridfile索引結構構建流程圖Fig.7 Design fl ow chart for Gridfile index structure

2.3 R-tree Gridfile 查詢與更新過程

R-tree Gridfile 自然鄰近查詢過程中輸入的是根結點S以及所要查詢的空間目標p所代表的空間范圍的MBR，輸出則是與p具有自然鄰近空間關系的集合U，p與U的關系記為nar(p，u)，U={u1，u2，…，un}，ui與p可能具有鄰近關系。一個空間目標p在R-tree Gridfile空間索引結構中的查詢過程可以分為以下幾個步驟。

1）查找與p對應的Gridfile，遞歸R-tree，用p所代表的空間范圍的MBR與R-tree Gridfile結點的MBR做比較，如果p.MBR∩node.MBR≠?，且結點是葉子結點，則表示找到了包含空間目標p的格網(wǎng)單元的地址。

2）找到p所對應的格網(wǎng)單元（i′，j′），得到格網(wǎng)單元的相關記錄信息，計算格網(wǎng)文件的偏移值4×sizeof(int)(j(j′-1)+i′)，然后讀取字節(jié)長度4×sizeof(int)，其中，j、i為格網(wǎng)的行列數(shù)，同時得到格網(wǎng)對應桶的首尾地址，Bucket文件在內(nèi)存空間中偏移值為locas1，讀取字節(jié)長度即為(locas2-locas1)。

3）解析桶中被讀取的二元組＜fid1，fid2＞，其中fid值即為候選目標的fid，得到與p可能滿足鄰近空間關系的完備集合U。即完成空間目標p在R-tree Gridfile空間索引結構中的查詢工作。

R-tree Gridfile的更新主要是針對待插入、刪除的空間目標，求出這些空間目標自身的MBR與R-tree Gridfile索引結構中格網(wǎng)單元所代表的空間范圍之間的空間關系的完備候選集合。然后再根據(jù)圖7中的算法對R-tree Gridfile空間索引結構部分重構。R-tree Gridfile空間索引結構在執(zhí)行對空間目標的索引或者對變化的目標進行更新的過程中并沒有對索引結構整體的更新，而是以葉結點的部分重構來代替整體的重構，實現(xiàn)了對索引結構的實時更新。

3 實驗與分析

本文實驗所用處理器為Inter(R)Core(TM)i5-3317U CPU@1.70GHz，所涉及的結構和算法在vs2013以及oracle 11g軟件環(huán)境下實現(xiàn)，所用來測試的數(shù)據(jù)均為離散面目標空間數(shù)據(jù)。格式為Arcgis中shp格式。詳細信息見表1。

表1 實驗數(shù)據(jù)詳細信息Tab.1 The details of experimental data

3.1 索引結構的物理性質比較

表2比較了R-tree Gridfile空間索引結構與SGI結構在索引構造過程中表現(xiàn)出的特性。

表2 索引結構的性質比較Tab.2 Comparison of properties of index structures

3.2 索引構建耗費時間和空間比較

構建R-tree Gridfile與SGI所消耗的CPU時間、所占磁盤空間大小與三角形數(shù)目之間的關系如圖8所示。R-tree Gridfile這種空間索引結構的優(yōu)點在于：①Unions Delaunay將表示相同鄰近空間關系的三角形合并成了一個Union，而SGI是以三角形為基本單位建立其自身的MBR在格網(wǎng)單元中進行空間索引，相比之下R-tree Gridfile能夠大量減少計算次數(shù)，節(jié)省了CPU工作時間；②SGI結構在索引構建過程中，需要將全部的三角形都存儲下來，需要較多的I/O時間。

而在占用磁盤空間方面，R-tree Gridfile索引結構不需要存儲三角形，它僅僅需要記錄Union所表示的二元組，即存儲空間目標鄰近目標的fid而SGI空間索引結構需要存儲全部的三角形，耗費磁盤空間遠大于R-tree Gridfile的構建過程所消耗的磁盤空間，因此，R-tree Gridfile明顯優(yōu)于SGI。

圖8 三角形個數(shù)與磁盤空間以及創(chuàng)建索引時間關系柱狀圖Fig.8 The relationship histogram about number of triangles with the disk space and the creation of the index time

3.3 索引結構更新分析

R-tree Gridfile空間索引結構的創(chuàng)建過程大致包含3個步驟：①Delaunay三角網(wǎng)的生成；②生成Unions Delaunay結構；③Gridfile結構的創(chuàng)建。圖9表示了在不同結點數(shù)的情況下這3部分的生成所對應的CPU耗費時間的相關情況以及生成R-tree Gridfile空間索引結構總共耗費時間。

圖9 結點數(shù)與索引構建時間關系Fig.9 The relationship between the number of nodes and index construction time

圖9 中的relation表明了創(chuàng)建R-tree Gridfile空間索引結構CPU耗費的時間和目標邊界結點的數(shù)量是大致呈線性遞增的關系，且可以看出③在這3個步驟中耗時最少，變化率較小，故其時間效率主要體現(xiàn)在步驟①、②中。今后如果要對該索引結構進一步優(yōu)化，則著重考慮步驟①、②的優(yōu)化。

3.4 索引的性能分析

隨機選擇R-tree的1葉子結點相對應的Gridfile(1550個結點，95個面目標)，在固定格網(wǎng)大小(50×50)的情況下查詢9個隨機點以及相關的數(shù)據(jù)見表3。

表3 R-tree Gridfile空間索引結構性能分析Tab.3 Performance analysis of spatial index structure for R-tree Gridfile

表3中，（行，列）表示查詢目標在格網(wǎng)空間中的行列號；所求目標數(shù)表示對空間目標查詢得到的鄰近空間目標的數(shù)量；CPU時間表示1次查詢所需要的時間；讀取的字節(jié)數(shù)表示1次查詢從磁盤空間中讀取的字節(jié)多少。由表3統(tǒng)計可知，平均一次查詢時間24.56 ms，每次選出3.56個鄰近空間目標；需要讀取34.56字節(jié)大小的數(shù)據(jù)。從數(shù)據(jù)分析來看，R-tree Gridfile 空間索引結構在數(shù)據(jù)庫中進行自然鄰近空間關系查詢表現(xiàn)出了較優(yōu)的性能。部分實驗結果如圖10所示。

圖10 部分實驗結果Fig.10 Some experimental results

4 結束語

在空間數(shù)據(jù)庫中直接使用現(xiàn)有索引來擴展自然鄰近查詢并不能保證結果的完備性，因此有必要將Voronoi/Delaunay結構考慮加入到索引結構的構建中。本文采用約束Delaunay三角網(wǎng), 建立面目標自然鄰近關系表達結構-Unions Delaunay，進而提出了一種空間索引結構-R-tree Gridfile來實現(xiàn)自然鄰居候選集提取。該索引結構能夠降低對磁盤空間占用，減少索引時的計算量以及實現(xiàn)了對葉結點的更新來代替整個索引結構的更新，實驗表明了其可行性。今后將對R樹固有的區(qū)域重疊和覆蓋的缺點以及Delaunay三角網(wǎng)和Unions Delaunay結構的生成算法做出進一步優(yōu)化，以提高索引效率。