基于Voronoi圖的方向區域查詢方法

劉潤濤，董慶宇，吳昊天

1.哈爾濱理工大學 信息與科學計算技術研究所，哈爾濱 150080

2.哈爾濱理工大學 理學院 數學系，哈爾濱 150080

方向區域查詢是根據給定條件，在空間數據庫中查找相應空間對象集的一種典型的空間查詢類型，在地理信息系統（GIS）中具有重要的作用，其廣泛應用在城市規劃、交通以及物流管理等各個領域。方向區域查詢的本質是根據所給定的方向及其他約束條件從數據集中找出方向區域內的所有空間對象。例如，若策劃修建一條公路，則需要確定在預定方向以及一定寬度的區域內有哪些建筑物需要被拆除。方向區域查詢因為其廣泛的應用前景，成為重要的研究內容。

與其他空間查詢方法一樣，當面對龐大的數據量時，效率成為了人們關注的問題。為了提高方向區域查詢的效率，學者們近年來提出了一些方法，其流程大致分為過濾和提純2個步驟，在過濾過程中不需要查詢區域的幾何信息進行完整的計算而是需要高效的索引結構將有可能在查詢區域內部的點加入候選集中，在該過程中可以舍去大量無關空間對象；對于提純過程，在利用候選集的基礎上進行嚴格的幾何計算從而得到完全在查詢區域內的正確結果集。由于提純過程中涉及復雜的幾何計算，故其通常比過濾步驟更加耗時。長時間以來，研究人員構造良好的索引結構使候選集減小或提出更有效的幾何驗證算法以降低提純的計算成本。

近年來，較多方向區域查詢方法被提出，其大多數是在R樹[1]與其擴展的基礎上進行的。這就使R樹的缺點被引入。Papadias等人[2-3]提出使用R樹結構檢索方向關系，但研究的都是絕對方向上的查詢（例如北、東）的索引機制和處理策略，為了實現絕對方向上的查詢，其方法使用范圍查詢策略（RQS），但具有一定局限性。為了克服在R樹索引上使用傳統的范圍查詢策略處理基于對象的方向查詢的局限性，Liu等人[4]提出基于開放形狀的策略（OSS），該策略在遍歷空間對象的過程中使用實際方向區域作為過濾器，從而盡早排除可能存在的錯誤結果。肖予欽等人[5]為了表示對象的MBR間的方向關系提出了一種四元組模型，同時利用上述模型和R樹提出了一種針對方向關系查詢的過濾方法，為了得到對象間的方向關系，根據MBR間方向關系的不同種類提出了相應的提煉方法，減少了計算消耗。張澤寶等人[6]在利用R樹以及四元組模型方向關系的基礎上提出了一種針對方向關系查詢的精過濾方法，在傳統的查詢流程基礎之上，加入了一個精過濾過程，減少了計算量。Liu等人[7]在已有方向查詢算法的基礎上，通過利用索引結構MB-tree，給出了針對方向查詢策略的剪枝規則，使訪問點的數量減少。Wei等人[8]利用包含空間對象內部和外部近似信息，提出了一種基于MRD-tree和開放形狀模型的方向查詢策略，該方法可以在過濾過程中排除大量無關對象。劉潤濤等人[9]利用MBR在MB-tree中有序的特點，提出了一種針對被查詢結點的MBR剪枝的規則，減少了I/O操作。王中輝等人[10-11]通過將方向以及空間距離關系相結合，提出了一種基于方向距離關系的方向空間查詢方法，但由于查詢模型的限制，查詢結果可能在某些情況下出現一些偏差。

R樹具有計算簡便等優點，但R樹在查詢過程中存在大量中間結點重疊和覆蓋的問題，即實際方向MBR區域遠大于實際方向所覆蓋的區域，從而使執行過程中訪問了較多不必要的結點造成候選集包含大量的錯誤結果，使整體查詢性能下降。為了提高方向區域查詢效率可采用性能更佳的結構。本文針對這個問題，將Voronoi圖結構引入方向區域查詢。

Voronoi圖[12-13]是計算幾何領域中的一個重要內容，在空間查詢等相關研究領域中得到了較多關注。此外，Voronoi圖與Delaunay三角剖分[14]互為對偶圖的關系已被廣泛地應用。Voronoi圖可以很好地表示空間數據的鄰近關系，同時具有矢量以及連續平鋪數據模型的基本特性，可以對空間數據進行很好的管理。鑒于Voronoi圖具有的良好拓撲結構和幾何性質，本文采用基于Voronoi圖的方法進行方向區域查詢。

為了獲得完整的幾何結構，本文利用Delaunay三角剖分形成Voronoi圖。首先，為了形成初始Delaunay三角網，在對點集求凸殼后，將凸殼點集進行Delaunay三角剖分，然后采用逐點插入的方式對插入點所影響的局部區域進行修改更新，利用已形成的Delaunay三角網生成Voronoi圖。對于給定的查詢對象，利用首結點與查詢對象連線形成的有向線段以及Voronoi圖可以通過鄰接生成點延展的特點確定查詢點位置，同時以查詢點位置為起點，利用Voronoi圖結構進行延展，減少了數據的訪問量，對于區域邊界，利用空間對象與查詢區域的關系分情況將相關點加入候選集中，減少對空間數據不必要的訪問，從而提高查詢性能。

1 基本定義及性質

定義1[15（]Voronoi圖）給定一組生成點P={p1,p2,…,pn}?R2,其中2＜n＜∞,且當(i≠j)時，pi≠pj。其中，i,j∈In={1,2,…,n}。以下公式給出pi的Voronoi區域：

其中，j≠i,j∈In,d(p,pi)表示點p與點pi間的最小距離（歐幾里德空間中點p和點pi間的直線距離）。其中點pi確定的Voronoi區域稱為點pi的Voronoi多邊形。

由V(P)={VP(p1),VP(p2),…,VP(pn)}構成的圖形稱為Voronoi圖。點pi稱為Voronoi生成點，共享相同的邊的Voronoi多邊形為鄰接多邊形，鄰接多邊形的生成點叫鄰接生成點。

圖1 Voronoi圖Fig.1 Voronoi diagram

定義2[12]（Delaunay邊）設三角網的邊集為E,對于其中的一條邊e,若存在一個圓經過e的兩個端點，且圓內不含點集中的任何其他點，則稱其為Delaunay邊。

定義3[12]（Delaunay三角網）若點集的一個三角網中所有的邊均為Delaunay邊，則稱該三角網為Delaunay三角網。

性質1[12]在點集S形成的Delaunay三角網中，每個Delaunay三角形的外接圓均不包含S中任意其他數據點；在點集S能夠形成的所有三角網中，Delaunay三角網中的三角形的最小角度是最大的。

性質2[16]Voronoi圖與Delaunay三角網對偶。

性質3[16]一個點集的Voronoi圖是唯一的。

性質4[16]在Voronoi多邊形中，每個Voronoi多邊形平均有6條邊，即每個生成點平均有6個鄰接生成點。

2 Voronoi圖存儲結構

近年來，有關構建Voronoi圖方法的研究很多，可以分為兩大類。其中一類是直接生成，即不經過其余流程直接根據點集構造Voronoi圖；另一類是間接生成，即利用性質1先對點集進行Delaunay三角剖分，然后構造Voronoi圖。直接生成Voronoi圖雖比間接生成Voronoi圖的效率要高，但間接生成Voronoi圖容易得到Voronoi多邊形的結構便于研究和存儲。本文將采用基于構建Delaunay三角網生成Voronoi圖的方法。首先，在形成初始三角網的基礎上，利用逐點插入法對點集中剩余點進行Delaunay三角剖分，形成點集的Delaunay三角網；其次，利用Delaunay三角網構造點集的Voronoi圖，同時在生成過程中，對點、邊等結構信息進行存儲。

2.1 Voronoi圖存儲結構的構成

在Voronoi圖存儲結構中各類結點的結構為：

Vor結點：(pi,Vor-Pointslist,Vor-EdgesList,Vor-NeighborsList)

其中Vor結點中pi表示該點坐標；Vor-Pointslist表示Voronoi多邊形頂點鏈表索引；Vor-EdgesList表示Voronoi邊鏈表索引；Vor-NeighborsList表示該點的鄰居鏈表索引；Vor-Point表示Voronoi頂點，其結點內p1表示該點坐標；PointArr表示共享該頂點的生成點；Vor-Edge表示Voronoi多邊形的邊，該結點內(pa,pb)表示該邊兩側的生成點，(ph,pt)表示該邊兩端點；Vor-Neighbor表示鄰接生成點（“鄰居”），其中pi表示該點的索引。

2.2 Voronoi圖存儲結構的形成

在構建Delaunay三角網的過程中，首先生成點集的凸殼，并將凸殼進行Delaunay三角剖分生成初始三角網；將點集中其余點通過逐點插入的方法加入三角網中從而完成最終Delaunay三角網的構建。

對于凸殼的構建存在較多算法，考慮時間消耗等因素，本文采用Graham凸包求解算法。該方法首先對點集進行預處理，然后利用預處理后的點集，根據兩點連線與第三點的方向關系判斷是否存在于結果集中，最終生成凸殼點集。為了形成初始的三角網，主要思想為：對已形成的凸殼進行Delaunay三角剖分，利用生成的凸殼信息，每次找到一個由兩條相鄰凸殼邊構成的三角形，同時確保沒有凸殼上的其他點被包含在此三角形的外接圓內部，對相關信息進行更新并記錄，依次執行，直至點集中最后剩下三個點，將各點相互連接形成三角形并記錄，最終生成初始的Delaunay三角網。

在初始的Delaunay三角網基礎上，采用逐點插入的方法形成點集的Delaunay三角網，如圖2所示，該方法主要思想為：從初始三角網中找出包含新插入點的三角形；以包含該插入點的三角形為起點，利用存儲的相關信息，找出外接圓包含新插入點的所有三角形，并形成三角形集，此三角形集的外邊界即為該插入點的影響區域，刪除三角形集中全部三角形，得到剖分空洞；將插入點與空洞中所有頂點依次進行連接，新產生的三角網滿足性質1，即符合Delaunay三角剖分準則。

圖2 插入點后Delaunay三角剖分Fig.2 Delaunay triangulation after insertion point

利用性質2，根據Delaunay三角網生成Voronoi圖，如圖3所示，其主要思想為：利用Delaunay三角網，對于凸殼上的邊，從該邊對應三角形外接圓圓心作指向該邊外部且垂直于該邊的射線；對于內部邊，則只需連接該邊兩側三角形外接圓圓心，依次處理Delaunay三角網中全部邊，最終可得到Voronoi圖。

圖3 利用Delaunay三角網生成Voronoi圖Fig.3 Using Delaunay triangulation to generate Voronoi diagram

3 連續單方向開放區域及判定點與區域關系

3.1 連續單方向開放區域

開放區域是指部分邊界被定義或邊界超出所規定數據空間范圍的幾何區域。連續單方向區域指的是開放區域朝一個方向進行延伸。如圖4（a）所示，給定查詢目標q、寬度w以及角度θ，從點q兩側分別延伸w形成的p1和p2分別為連續單方向的兩個起始點，n1和n2為分別以p1和p2為起始點的方向向量。如圖4（b）和（c）所示θ∈[0,360]，且設定p1(x1,y1)和p2(x2,y2)兩點滿足x1＜x2或x1=x2,y1＞y2。

圖4 方向區域查詢模型Fig.4 Direction area query model

3.2 判斷點與區域關系的條件

定理1已知一有向線段上的兩點p(x p,yp),q(x q,yq),對于空間上任意一點s(x s,ys)，設：

若F(p,q,s)＞0，則點s在該有向線段的左側；

若F(p,q,s)＜0，則點s在該有向線段的右側；

若F(p,q,s)=0，則點s在該有向線段上。

對于如圖4（a）所示的方向區域查詢模型，若空間中任意一點s(x s,ys)在查詢區域內則應同時滿足在p1p2的左側，n1的右側，n2的左側。根據定理1基于如上討論得到以下判定規則：

判定規則1對于空間中任意一點s(x s,ys)，設點q1為n1上除點p1外任意一點，點q2為n2上除點p2外任意一點。若有F(p1,p2,s)≥0,F(p1,q1,s)≤0,F(p2,q2,s)≥0成立，則點s位于查詢區域內。

4 基于Voronoi圖的方向區域查詢

根據所給定的查詢對象q以及所確定的查詢區域，利用Voronoi圖的拓撲結構與幾何性質，進行基于Voronoi圖的方向區域查詢。首先根據Voronoi圖結構找到查詢對象所在位置，然后根據不同位置，按照規則將相應空間對象加入候選集，通過判斷空間對象與查詢區域的位置關系，根據規則加入候選集并判定是否為正確結果，從而得到查詢結果集。

為了獲得初始候選集，根據q所在位置分2種情況討論：（1）查詢對象位于生成點Voronoi多邊形內；（2）查詢對象位于Voronoi邊上或位于Voronoi頂點上。為了使初始候選集中一定包含查詢區域內部對象或與位于查詢區域內部對象相關聯的對象，給出以下判定規則。

判定規則2若對于任意pi∈S有q∈pi.VoronoiArea,則將pi.Vor-NeighborsList中對象加入候選集，其中S為數據點集。

判定規則3若對于任意pi∈S有q∈pi.Edge&q?pi.Vor-Point，則將pi.Edge.(pa,pb)加入候選集；若q∈pi.Vor-Pointslist則將pi.Vor-Point.PointArr中對象加入候選集，其中S為數據點集。

根據點集中各點與方向查詢區域的位置關系分2種情況討論：

（1）該點位于方向查詢區域內；（2）該點不在方向查詢區域內，但該點的Voronoi頂點在方向查詢區域內。

若假設pi∈QueryArea（查詢區域），則存在(pk∈pi.Neighbors)∈QueryArea或(pk∈pi.Neighbors).Neighbors∈QueryArea；若pi?QueryArea,但(pi.PointArr)∈QueryAre,則可能存在(pk∈pi.Neighbors)∈QueryArea。由于初始候選集中一定包含情況（1）或（2）的點，故只需考慮以上兩種情況即可?；谝陨嫌懻摰贸鲆韵屡卸ㄒ巹t。

判定規則4對于一點pi∈S若pi∈QueryArea，則將點pi加入結果集的同時將pi.Vor-NeighborsList中所有點加入到候選集，其中S為數據點集。

判定規則5若pi?QueryArea，但存在pi.Vor-Edge∩QueryAre，只將pi.Vor-NeighborsList中所有點加入到候選集。

定理2利用Voronoi圖結構，從給定查詢對象出發根據以上判定規則可以使查詢區域中的點完全在候選集中，從而保證輸出準確結果集。

證明在確定查詢對象具體位置后，根據判定規則2和判定規則3可以確保使初始候選集中包含位于查詢區域內的對象或盡管位于查詢區域外但其Voronoi點在查詢區域內的空間對象，之后根據判定規則4和判定規則5以及初始候選集中的點，利用Voronoi圖結構進行擴展，使得查詢區域內部對象以及與查詢區域邊界有關聯的對象完全加入候選集。

根據以上判定規則以及定理2，本章提出基于Voronoi圖的方向查詢算法的主要思想為：首先判斷查詢點位置，該過程為將存儲結構首結點與查詢點連接生成向量，找到首結點與其鄰接生成點連線中與向量夾角最小的為下一個點，從而替換首結點，依次執行，直至確定查詢點位置；在確定位置后，根據規則1和規則2將相應點放入候選集中，之后從候選集中依次取出點，將區域內的點加入結果集中，根據規則3和規則4向候選集中加入新的點，直至輸出完全結果集。在以上討論的基礎上，給出基于Voronoi圖的方向查詢算法，如算法1所示。

算法1Dir_Area_Query_Vor(Vor List,q,w,θ)

如圖5所示，在基于Voronoi圖的方向區域查詢過程中，確定查詢點具體位置后，建立區域模型，形成兩個向量與一條線段所劃定的查詢區域，且標記√的Voronoi多邊形為查詢過程中被加入候選集中的點。

圖5 查詢過程模型Fig.5 Query process model

5 實驗結果與分析

將本文給出的基于Voronoi圖的方向區域查詢算法與文獻[7]中的基于MRD-樹的方向區域查詢算法進行比較。實驗環境為：

（1）硬件環境：1.5 GHz CPU、4 GB內存、100 GB以上磁盤的個人計算機。

（2）軟件環境：Windows 10 Professional操作系統，使用Visual Studio 2012編程實現。本文使用的數據集均為系統隨機生成。

對于不同條件變量，本文進行以下測試項目：

（1）針對基于Voronoi圖算法以及基于MRD-樹算法在數據量不同情況下，對方向區域查詢時所花費的時間以及I/O消耗進行比較。

（2）針對基于Voronoi圖算法以及基于MRD-樹算法在數據集密度不同情況下，對方向區域查詢時所花費的時間以及候選集中非必要數據量進行比較。

圖6、圖7給出了數據集大小對于算法執行的影響，其中查詢角度固定為30°，數據集大小為1×104～1×105，其中數據集中坐標值大小限制在0～1×105。由圖6中可見，基于R-樹的查詢方法執行時間最長，其次為基于MRD-樹的查詢方法和基于Voronoi圖的查詢方法，且隨著數據集逐漸變大時間消耗差距變大，這是因為基于Voronoi圖的查詢方法能夠避開無效結點確定查詢點位置，并且在查詢過程中通過減少候選集中點的數量達到了減少大量幾何計算的目的，從而加快了查詢速度。圖7給出了數據集大小對于I/O代價的影響，對于不同數據規模，基于Voronoi圖的方向區域查詢方法的代價低于其他兩種方法。這是因為基于Voronoi圖的查詢方法在查詢過程中能夠減少更多非必要結點的訪問使I/O代價降低。

圖7 數據量變化對I/O的影響Fig.7 Impact of data volume changes on I/O

表1給出了三種方法隨著數據量變化各方法查詢過程中候選集內數據量的對比，隨著數據量不斷增加，其他兩種方法查詢過程中候選集內數據量均大于基于Voronoi圖方向區域查詢方法，故該算法對于減少非必要數據點的訪問效果較好且優于其余兩種算法。

表1 三種算法的查詢對比Table 1 Query comparison of three algorithms

圖8、圖9給出了方向區域查詢中角度對于算法執行的影響，數據集大小為5×104，其中查詢角度為0°～180°。由圖8可見當查詢角度不斷變化時，基于R樹的查詢方法執行時間最長，其次為基于MRD樹以及基于Voronoi圖的查詢方法，且該狀態一直持續。由圖9可見基于Voronoi圖的查詢方法的I/O消耗始終優于其他兩種查詢方法，且在0°～90°區間內基于Voronoi圖查詢方法與其他兩種方法消耗差距最大，對應的角度為45°，在90°～180°區間內基于Voronoi圖查詢方法與其他兩種方法消耗差距最大對應的角度為135°，這是因為基于R樹以及MRD樹的結構在查詢過程中受到角度的影響造成查詢過程中訪問的MBR數量不同，且在45°和135°時訪問MBR數量最多，從而導致I/O消耗增加，而基于Voronoi圖的查詢方法不受查詢角度限制。

圖8 查詢角度變化對CPU消耗的影響Fig.8 Impact of query angle changes on CPU consumption

圖9 查詢角度變化對I/O消耗的影響Fig.9 Impact of query angle changes on I/O consumption

6 結束語

本文基于對空間數據方向區域查詢的研究，提出了一種基于Voronoi圖的方向區域查詢方法，該方法利用Voronoi圖的存儲結構，根據Voronoi圖幾何結構以及可以通過鄰接生成點延展的特性，大幅度減少了在確定查詢對象位置以及查詢過程中非必要結點的訪問，從而達到了提高方向區域查詢效率的目的且得到了準確的查詢結果。理論分析和實驗結果表明，該算法能夠準確獲得查詢結果并具有較好的查詢性能。未來將對基于Voronoi圖的其他種類查詢進行研究。