基于多層Voronoi圖索引的非點型空間對象區域查詢方法研究

明 梓，劉 偉，李 旸，崔俊杰，劉 剛，李佳惠，雷夢婷

（1.湖北工業大學 經濟與管理學院，湖北 武漢 430068；2.長江信達軟件技術（武漢）有限責任公司，湖北 武漢 430014；3.中國地質大學（武漢）地理與信息工程學院；4.中國地質大學（武漢）計算機學院，湖北 武漢 430078；5.湖北工業大學 計算機學院，湖北 武漢 430068）

0 引言

城市化進程的加快帶來了交通擁堵、空間環境惡劣等問題，給我國智慧城市的建設帶來了挑戰［1-4］。合理開發與利用城市地理空間大數據，借助物聯網和人工智能等技術對城市地理空間資源進行智能管控與高效調度是解決上述問題的有效途徑。在面向城市地理空間大數據的地理信息系統（Geographic Information System，GIS）建設中，高效的空間查詢技術是關鍵基礎［5-9］。其中，區域查詢方法是應用最廣泛的一類查詢方法，可以快速檢索到指定區域內包含的全部地理空間對象（例如建筑、植被、公共設施、車輛等），幫助城市管理者了解城市地物的分布情況，從而為其提供決策支持。

基于空間邊界約束的查詢通常被稱為空間區域查詢，即從該數據庫中檢索出一個指定區域內的所有數據對象，這個目標區域可以是任何形狀的封閉幾何圖形。目前主流區域查詢算法均基于R-tree 提出，但由于R-tree 在面對大規模、非均勻分布的城市空間大數據時會出現節點重疊、結構失衡等一系列問題，以R-tree 索引為基礎的區域查詢算法很難有理想表現。因此，MVD（Multi-layer Voronoi Diagrams）索引被提出，其通過多層Voronoi 網絡結構替代傳統樹形結構，有效規避了上述問題［5］。以MVD 為基礎的區域查詢算法在面對城市空間大數據時展現出更高的查詢效率（即查詢算法的響應速度），但其無法直接對非點型數據進行索引，因此基于MVD 的區域查詢方法不支持非點型空間數據。

針對上述問題，本文基于MVD 索引提出一種針對非點型空間對象的區域查詢技術框架：首先通過最小外包圓（Minimum Bounding Circle，MBC）對空間對象進行擬合，實現MVD 索引對非點型空間對象的存儲管理；然后根據空間對象最小外包圓的半徑上界對查詢區域進行邊界拓展，實現MVD 索引對非點型空間對象的區域查詢，進而提出MVD-Polygon 算法。為進一步優化MVD-Polygon 算法的查詢效率，采用空間對象尺度對數據進行分級管理，從而加速查詢過程，并將優化后的MVD-Polygon 命名為MVDPolygon-Grade。為驗證該方案的有效性，將MVD-Polygon、MVD-Polygon-Grade 與基于R-tree 的主流區域查詢算法Multi-step 進行性能比較，結果表明MVD-Polygon 算法擁有更高的查詢效率。

1 相關研究

空間區域查詢最早由Willard［10］提出，并提供了一種以O(nlog64)復雜度求解的方案，其中n為數據庫中的數據總量；而后，Paterson 等［11］基于B-tree 提出一種計算復雜度為O(k·logn+s)的求解方案，其中k為多邊形邊的數量，s為結果集大小。自R-tree 索引被提出后，絕大多數區域查詢方法都開始采用該索引作為基礎來實現。為減少PIP（Point in Polygon）驗證次數，Kriegel 等［12］基于R-tree 索引提出一種通過兩級過濾策略實現的空間區域查詢算法Multi-step，該算法通過查詢區域的外包近似形從R-tree 中檢索出一個候選集，然后對候選集中的對象逐一過濾，篩選出最終結果集。R-tree 內部的基本單元都是空間正交矩形，而正交矩形之間的空間關系運算非常簡單快速，因此一般情況下都是利用正交的最小外包矩形（Minimum Bounding Rectangle，MBR）來構建查詢區域的近似形。在Oracle Spatial 組建中，區域查詢也是基于R-tree 實現的，但其不需要利用空間近似形進行初次過濾，而是直接利用查詢范圍進行檢索［13］。在這種區域查詢算法的執行過程中，雖然部分節點與查詢區域之間的空間拓撲關系運算成本會有所增加，但總體I/O 成本有效降低。

城市地理空間數據的多中心非均勻分布會加劇Rtree 索引的節點重疊，因此在面向城市地理空間大數據的GIS 系統中，基于R-tree 實現的區域查詢算法需要訪問大量索引中間層節點，并產生大量冗余空間關系驗證，進而導致基于R-tree 的Multi-step 區域查詢算法在面對海量對象、空間關系復雜的場景中存在查詢效率較低的問題。為進一步提升復雜場景下的算法查詢效率，Li等［14］基于復合型索引VoR-tree 提出一種利用Voronoi 圖實現的區域查詢方法Voronoi-Region，并將該方遷移至高性能的多層網絡結構索引MVD 中［5］。借助MVD 的非樹形結構，該算法在避免訪問大量中間節點的同時削減了絕大部分冗余數據點的訪問和驗證，有效提升了海量對象以及復雜空間關系場景中針對點型數據的區域查詢效率。然而，Voronoi圖的構建需要以一個離散點集合為基礎，以Voronoi 圖為基礎部件的MVD 索引僅支持點型數據管理，即相對應的區域查詢方法無法適用于非點型數據檢索。

為此，本文基于MVD 索引提出針對非點型數據的管理方式和相應的區域查詢算法，以解決MVD 索引不支持非點型數據管理以及其對應的區域查詢算法無法對非點型數據進行區域查詢的問題，進而改進目前主流算法在海量對象與復雜空間關系場景下對非點型數據進行區域查詢時效率不足的問題。

2 基于邊界擴展的MVD區域查詢技術

2.1 總體技術框架設計

基于MVD 索引實現針對非點型空間數據的高性能區域查詢方法需要解決兩個重點問題：第一是如何實現MVD 索引對非點型空間對象的存儲管理？本文基于MVD索引的點對象與非點型空間對象之間的關系構建起兩種映射關系，完成對非點型空間對象的管理；第二是如何基于MVD 索引設計針對非點型空間對象的區域查詢方法？本文采用引入緩沖區的方法構建候選集，并對候選集中的對象進行空間關系驗證，得到最終結果集。同時基于初始查詢邊界拓展查詢邊界，實現MVD 索引對非點型空間對象的查詢，并基于空間對象尺度的數據分級方法加速查詢過程。總體技術框架見圖1（彩圖掃OSID 碼可見，下同）。

Fig.1 Overall technical framework圖1 總體技術框架

2.2 非點型空間對象存儲管理方法

針對非點型空間對象的管理方式需注意兩個方面：①MVD 索引結構是以點對象為基礎構建的，非點型空間對象需基于MVD 索引結構進行管理；②MVD 索引結構管理非點型空間對象時需完整地存儲非點型對象數據。

針對第一個方面，MVD 索引結構以點對象為基礎構建，需要選擇某個點來代替非點型空間對象構建索引結構。本文選擇非點型空間對象的質心代替整個對象構建MVD 索引結構，構建質心與整個對象一對一的映射關系。非點型空間對象與質點映射關系如圖2所示。

Fig.2 Mapping relationship between non-point spatial object and centroid圖2 非點型空間對象與質心映射關系

針對第二個方面，非點型空間對象包含眾多數據，如對象的邊界線數據、尺度數據、屬性數據等。在完成這些數據的存儲后，本文根據質心與這些數據的關聯關系構建一對多的映射關系。

以上兩種映射關系可以通過非點型空間對象的質心ID 進行關聯。其中，第一種映射關系通過非點型空間對象的質心構建MVD 索引，然后通過針對點對象的空間查詢方法進行區域查詢，可以得到非點型空間對象的質心構成的點集；第二種映射關系根據點集中的點對象ID 與其對應的非點型空間對象ID 的映射關系即可查詢到整個非點型空間對象的全部數據。

2.3 基于邊界擴展技術的MVD索引區域查詢方法

基于邊界擴展技術的區域查詢方法總體流程如圖3所示。該方法主要包含兩個核心技術，分別為基于MBC半徑的查詢區域邊界擴展方法和基于擴展邊界的候選集驗證方法。基于MBC 半徑的查詢區域邊界擴展方法的主要思路為通過引入緩沖區來增大區域查詢范圍，使候選集包含所有查詢結果；基于擴展邊界的候選集驗證方法的主要思路為通過對候選集中的對象進行空間關系驗證來篩選出最終結果集。

Fig.3 Overall process of region query method based on boundary extension technology圖3 基于邊界擴展技術的區域查詢方法總體流程

2.3.1 基于MBC半徑的查詢區域邊界擴展方法

選擇非點型空間對象的質心構建MVD 索引后，如果僅直接按照將質點視為整個非點型空間對象的思路進行區域查詢，則會造成質點在查詢區域外，但其實際對應的非點型空間對象在查詢區域內的情況，本文將其稱為漏檢問題。針對該問題，本文在原有區域查詢邊界的基礎上引入緩沖區來構建候選集。為表述方便，定義以下概念：①空間對象尺度，指空間對象最小外包圓的半徑值，用R 表示，點對象的尺度為零；②緩沖區尺度，指構建緩沖區過程中在查詢邊界外側所作的平行線與查詢邊界的垂直距離，用L表示；③數據集尺度，數據集中全體空間對象尺度的最大值代表該數據集的尺度，即Rmax=Max{R1，R2，R3，…，Rn}，用Rmax表示。

以緩沖區邊界為基礎執行對點對象的區域查詢方法，得到由質心構成的點集，點集中的質心所對應的非點型空間對象構建成了候選集。只要緩沖區邊界可以包含所有結果，便可以避免漏檢現象。因此，在初始區域查詢邊界的基礎上引入何種尺度的緩沖區是關鍵問題［15-17］，基于極限思想，當緩沖區尺度大于或等于數據集中最大尺度的非點型空間對象時，緩沖區邊界恰好包含所有結果。以圖4為例，尺度最大的非點型空間對象為4 號，其質心為p點，尺度為Rmɑx，如果僅看區域查詢邊界，p點在區域查詢邊界之外，當緩沖區尺度L等于Rmɑx時，緩沖區邊界可以包含所有區域查詢的結果（p點在緩沖區邊界內），這些結果構成了針對非點型空間對象的區域查詢算法的候選集。

Fig.4 Schematic diagram of maximum value of buffer scale圖4 緩沖區尺度極大值示意圖

綜上可知，基于初始查詢邊界引入合適尺度的緩沖區便可使所有結果包含在緩沖區范圍內。對于區域查詢邊界，分別在其外側作距邊界線一定距離的平行線可生成緩沖區邊界［18］。根據查詢區域原始邊界的頂點坐標和緩沖區尺度可以求得每個原始頂點到其在緩沖區邊界上對應頂點間的向量d，從而得到緩沖區邊界上所有頂點的坐標。每個頂點對應的向量d的計算步驟如下：

（1）構建單位向量。如圖5 所示，對于當前區域查詢邊界上的點p來說，其與左右相鄰點n、m構成兩個向量，設向量為n，向量為m，其單位向量分別為a和b。

Fig.5 Schematic diagram of buffer intersectionc圖5 緩沖區交點示意圖

（2）計算擴大后的向量。計算出單位向量后，由于兩個方向的向量大小模長均為1，將a和b向量相加并取反得到外擴方向上的單位向量c。

（3）計算緩沖區邊界上的交點。緩沖區尺度為L，取向量c的反向向量-c與m的角度，進而計算向量-c與向量m的距離dis。計算dis與L的比值，根據比值計算向量c方向上的目標向量d，計算方法見式（1）。最后根據兩個向量求出目標點q。

基于數據集尺度引入對應尺度的緩沖區，然后利用緩沖區邊界對空間對象集對應的質心點集執行范圍查詢，即可得到充分包含所有結果集對象的候選集。具體步驟為：①獲取區域查詢范圍邊界；②基于原始區域查詢邊界引入數據集對應的緩沖區，得到緩沖區邊界；③基于緩沖區邊界進行針對點數據的區域查詢，得到質心集合；④基于“2.2”節中的第一種映射關系即可通過質心集合中的質心ID 查詢到質心對應的非點型空間對象，這些非點型空間對象構成了候選集。

2.3.2 基于擴展邊界的候選集驗證方法

當候選集構建完成后，需要對其中的對象進行過濾，以得到最終結果集，其中過濾主要是驗證結果集中非點型空間對象與區域查詢邊界之間空間關系的過程。候選集中的非點型空間對象可分為兩類：第一類是質心在區域查詢邊界內的對象，第二類是質心在區域查詢邊界與緩沖區邊界之間的對象。如圖6 所示，1、2、3 號對象為第一類對象；紅點處為第二類對象。

Fig.6 Schematic diagram of two types of non-point spatial objects圖6 兩種非點型空間對象示意圖

針對第一類對象進行空間關系驗證，如果某個空間對象的質心在區域查詢邊界內，說明這個對象一定與查詢邊界存在相交或包含關系，屬于區域查詢的結果集，只需要進行一次針對點對象的區域查詢即可得到由質心構成的點集，點集中的點所對應的非點型空間對象即為構成結果集的對象。

針對第二類對象進行空間關系驗證，只需要判斷是否至少滿足以下兩個條件之一：①該空間對象至少存在一個邊界頂點在查詢區域內部（避免邊的重合）；②該空間對象的邊界與查詢區域邊界相交。本文采用引射線法判斷二者是否相交［19-20］，如果存在相交關系，則將其納入結果集中。

2.3.3 算法步驟

基于MVD 索引的針對非點型空間對象的區域查詢算法步驟為：

2.4 基于空間對象尺度分級的索引構建策略

由上文可知，基于初始查詢邊界引入合適尺度的緩沖區便可將所有結果包含在緩沖區范圍內。如果數據集中的非點型空間對象尺度相近，引入緩沖區進行區域查詢后候選集中只包含少量冗余對象。然而在城市空間查詢場景中，數據集中的非點型空間對象尺度不一定相近，例如一個城市的人工湖、大型商場、一個電話亭的尺度完全不在一個數量級，根據城市內最大尺度對象的尺度引入緩沖區后，區域查詢的候選集中會包含大量冗余對象。如果根據尺度對數據集中的對象進行分類，手動將尺度相近的對象分在同一個數據集中，例如將電話亭、汽車等尺度在米級別的對象分到一個數據集中，將商場、學校等百米級別的對象分到另一個數據集中，以此構成若干個子數據集，并分別引入對應尺度的緩沖區進行查詢，則可有效減少候選集中的冗余對象。

如圖7 所示，以澳門市建筑輪廓的一部分為研究對象構建各尺度子數據集的候選集，建筑對象構成了數據集，將數據集內的對象手動分為大、中、小尺寸的3 個子數據集，并分別引入相應尺度的緩沖區。其中，圖7（a）為數據集未進行尺度劃分的情況，引入整個數據集中尺度最大的空間對象的尺度（圖中5 號對象的尺度）作為緩沖區邊界，質心在緩沖區內的所有非點型空間對象均被納入到候選集中，共包含20 個對象，其中1、2、3、4 號對象為區域查詢的最終結果。圖7（b）、（c）、（d）為3 個不同尺度的子數據集引入對應尺度緩沖區后的結果。子候選集中的對象個數分別為6、2、0，對子候選集取并集構成最終候選集，共包含8 個對象，且1、2、3、4 號對象均包含其中。可以看出，對數據集進行分級預處理可有效減少候選集中的冗余對象。

Fig.7 Schematic diagram of candidate subset construction of sub data sets of all scales圖7 各尺度子數據集候選集構建示意圖

3 實驗方法與結果分析

為驗證本文提出的針對非點型空間對象的區域查詢算法MVD-Polygon-Grade（以下簡稱MPG 算法）的性能，以及基于空間對象尺度的數據分級管理方案的查詢效率，以基于R-tree 的Multi-step 算法（以下簡稱MS 算法）和MVD-Polygon（以下簡稱MP 算法）算法為對照進行評估實驗。本實驗旨在比較3 種算法的時間效率，即算法完成一次查詢所需要的時間，所需時間越少，算法效率越高。為減少誤差，實驗結果經過50次運行后取算數平均值得到。

3.1 實驗環境配置

實驗環境主要包括軟件和硬件兩個方面，詳細配置如表1所示。

3.2 數據集

基于尺度相近的對象放到同一個子數據集的原則，本研究根據澳門市12 482 個建筑輪廓的面數據將城市建筑分為5類，構建5個子數據集。具體信息見表2。

Table 2 Information of sub datasets at different scales表2 不同尺度子數據集信息

3.3 結果分析

如圖8 所示，澳門市建筑輪廓數據集包含12 482 個建筑輪廓的面數據，這些面數據共由225 807 個邊界點構成，平均每個面數據由18 個點表示，符合非點型空間對象的特征。

Fig.8 Outline of buildings in Macao圖8 澳門市建筑輪廓

為研究區域查詢邊界的規則程度對算法效率的影響，分別構建頂點為4～6 個和20～30 個的多邊形作為區域查詢邊界，兩組多邊形分別構建50 個。為減少查詢面積對實驗結果的影響，本組實驗保證查詢區域邊界的最小外包圓面積相同，查詢面積依次為3 km2、5 km2、8 km2、12 km2、16 km2。由圖9 可以看出，無論區域查詢邊界是否規則，在相同查詢面積下，MPG 算法比MS算法和MP 算法具有更高的效率，但MPG 算法比MS 算法更易受到區域查詢邊界規則程度的影響，區域查詢邊界越復雜，MPG 算法效率下降得越快。這是由于在MPG 算法的結果集構建過程中，第一類空間對象是基于高效MVD 針對點數據的區域查詢算法而來，本身就屬于結果集，只需要很低的時間成本即可完成第一類空間對象的確定；而判斷第二類空間對象是否屬于結果集需要依次對其進行空間關系驗證，相對耗時，且區域查詢邊界越復雜，空間關系驗證所需時間成本越高；區域查詢面積越小，第二類空間對象占整個候選集的比例越大。基于以上原因，MPG 算法基于空間對象尺度對數據進行分級管理，以確保第二類空間對象很少。MP 算法沒有基于空間對象尺度對數據進行分級管理，導致有大量第二類空間對象需要進行空間關系驗證，因此與MS 算法相比，MP 算法在區域查詢面積較小時并未體現出明顯優勢。隨著區域查詢面積的增大，第二類空間對象占候選集對象的比例逐漸降低，MP 算法效率逐漸接近MPG 算法。

Fig.9 The influence of the rule degree of region query boundary on the efficiency of region query圖9 區域查詢邊界規則程度對區域查詢效率的影響

為驗證查詢區域面積對算法效率的影響，本組實驗的區域查詢邊界形狀設置為正交矩形，查詢位置隨機，查詢區域面積分別為3 km2、5 km2、8 km2、12 km2、16 km2，分別占整個數據分布區域的6.2%、10.4%、16.7%、25%、33.3%，每種面積下的查詢次數均為50 次，取算數平均值作為最終結果。由圖10 可以看出，無論何種查詢面積，MPG 算法均比MS 算法和MP 算法有更高的查詢效率。在區域查詢面積較小的情況下，MP 算法和MS 算法的效率并未表現出顯著差異；在區域查詢面積較大的情況下，MP 算法的效率接近于MPG 算法，強于MS算法。

Fig.10 The influence of query area on the efficiency of region query圖10 查詢區域面積對區域查詢效率的影響

4 結語

為合理開發與利用城市地理空間大數據，本文針對MVD 索引只能管理點型數據而無法直接針對非點型數據進行區域查詢的問題，設計提出了一種基于邊界擴展技術的區域查詢算法實現框架。該框架通過最小外包圓對空間對象進行擬合，基于MVD 索引實現非點型空間對象的區域查詢，并基于空間對象尺度對數據進行分級管理以提高查詢效率。利用澳門市城市建筑輪廓數據進行驗證實驗，結果表明，在相同查詢面積、查詢邊界復雜程度條件下，本文提出的MVD-Polygon-Grade 算法比Multistep 算法和MVD-Polygon 算法查詢效率更高，且數據規模越大、查詢面積越大，數據尺度分級層次越明顯，MVDPolygon-Grade 算法的區域查詢效率越高。本研究提出了從點對象拓展到非點型空間對象的通用數據管理思路和區域查詢方法，為進一步挖掘現有索引結構的數據管理潛力提供了支撐。然而該方法仍存在改進空間：①MVDPolygon-Grade 算法的分級方法為前期數據處理過程中的手動粗糙分級，未來將設計針對數據集的最優分級方法，以保證各個子數據集內的數據方差最小，數據集間方差最大，使候選集驗證過程中產生最少冗余，進一步提升算法效率；②主要驗證了查詢面積、查詢邊界復雜程度對MVD-Polygon-Grade 算法的影響，未來將研究更多因素（如空間對象的密集程度）對該算法的影響，以拓展其應用場景。