一種基于泰森多邊形的最近服務點搜索方法

魏金占，易桂軒

(1.欽州學院，廣西 欽州 535000； 2.武漢市測繪研究院，湖北 武漢 430022)

1 引 言

服務點是指電子地圖上的某個地標、景點，用以標示出該地所代表的政府部門、各行各業之商業機構(加油站、百貨公司、超市、餐廳、酒店、便利商店、醫院等)、旅游景點(公園、公共廁所等)、古跡名勝、交通設施(各式車站、停車場、超速照相機、限速標示)等處所，用于提供服務；興趣點則是接受服務點所提供服務的地點，可以是某個場所地點或是某用戶的當前坐標[1，2]。

最臨近服務點的搜索方法是指搜索服務點中離興趣點最近的一個，一般多采用興趣點到周邊服務點的直線距離逐個搜索，算法各異。常見的算法為根據一定范圍搜索興趣點周邊的服務點，之后逐個判定距離大小，最小者即為搜索結果[3，4]。這類方法原理簡單，但存在搜索范圍過大，效率低下的弊端。此外通過興趣點找尋服務點，興趣點的數量一般遠大于服務點，如地塊到最鄰近水源問題，一個縣域地塊數量多以萬計，因此該種模式的搜索從根本上就決定其效率低下。

2 解決思路

傳統的最鄰近服務點搜索多由興趣點自身發起，如搜索地塊到最鄰近水源這類問題，其需要對每個地塊逐一搜索。而且一旦服務點如水源發生變化，必須進行重新搜索，算法具有一定的不確定性和效率不高的弊端。

傳統的最鄰近服務點搜索多以興趣點作為中心，搜索該點在一定范圍內到鄰近服務點的距離，選擇最小距離為最終結果。對于興趣點到兩個臨近服務點的距離判定，可采用兩服務點連線，取其中心點垂線作為劃分依據，當服務點和興趣點都在該垂線一側，由中垂線的定義可知，該興趣點與最鄰近服務點位于垂線同一側時表明該興趣點與該服務點較近。而基于中垂線的影響范圍確定就是泰森多邊形構建的原理，因此本文結合泰森多邊形原理和空間分析技術，提出一種新的最鄰近服務點搜索算法。該技術首先通過泰森多邊形技術構建服務點(區)的服務范圍，通過服務點反向查詢其服務范圍覆蓋的區域，如果覆蓋區域包含發出請求的興趣點，則認為該服務區對應的服務點即為該興趣點的最鄰近服務點。該原理與移動蜂窩基站技術類似，將各個服務區服務范圍劃分為若干子區域，一旦客戶進入該區域，即認為興趣點的最臨近服務區就是該服務區。

基于此，本文認為該搜索方法的核心技術在于服務區(點)服務范圍的構建及后期的空間分析部分。地理信息技術中泰森多邊形是以兩點連線的中垂線相交所得多邊形范圍來確定的，其本質就是基于質心點影響范圍的確定。下文將結合實例，闡述該方法具體實現過程及效率對比分析。

3 實施案例

以土地利用分析中地塊最臨近水源搜索為例，闡述如何利用上述思路實現。眾所周知土地利用中對于地塊灌溉水源的確認是非常重要的，一般方法多通過地塊中心點，搜索周邊水源模式來實現[5]。因為地塊數量的巨大，搜索參數選取的不確定性，搜索效率不盡人意。根據最臨近水源判定標準可知，最近水源面中心點與地塊的中心點連線長度是否最小決定其是否滿足最臨近水源判定標準。基于此，可以認為地塊的最近水源意味著該地塊在該水源的灌溉范圍，因此可以逆向思維，通過水源的灌溉范圍和地塊中心點的空間關系來確定地塊最臨近水源。該思路的核心在于水源的覆蓋范圍確定，因此可做如下考慮：以水源中心點為核心，逐漸外擴構建每個水源點的覆蓋范圍。該思路與泰森多邊形的構建過程一致[6～10]，因此可以借助該原理實現水源灌溉范圍的確定，之后通過空間關系確定每個地塊最臨近水源信息。

本文以超圖地理信息系統為實現平臺，具體步驟為：

(1)完整性檢查，將水源面狀數據轉換為點狀數據并記錄對應的屬性信息；

①檢查水源面狀數據屬性信息及幾何信息的完整性，如圖1所示；

圖1 整體區域包括地塊1以及水源Ⅰ、Ⅱ、Ⅲ

②將水源范圍面狀數據進行中心點提取，得到水源點并記錄該水源的屬性信息；

③將地塊范圍面狀數據轉換為地塊中心點數據，得到地塊點并記錄該地塊的屬性信息；

(2)基于各個水源中心點構建不規則三角網；

將各個水源中心點構建不規則三角網，確定區域內水源覆蓋范圍，確保每處水源被三角網覆蓋，如圖2所示；

圖2 構建的不規則三角網

(3)構建泰森多邊形，確定水源覆蓋范圍

以不規則三角網為準構建泰森多邊形，將整體區域劃分為多個子區域，各個水源中心點分別位于對應的子區域中，該子區域即為對應水源的服務范圍。

(4)求解最鄰近水源

通過北京超圖地理信息平臺將地塊中心點與構建泰森多邊形后的整體區域進行空間求交，獲得地塊中心點所在的子區域，則中心點同樣位于該子區域的水源即為地塊最臨近的水源，如圖3所示水源Ⅰ、Ⅱ、Ⅲ；地塊1位于水源Ⅰ對應的子區域，則地塊最臨近的水源為水源Ⅰ，求解最臨近水源。

圖3 地塊1位于水源Ⅰ對應的子區域，則地塊最臨近的水源為水源Ⅰ

(5)地塊變化時最鄰近水源求解

將該整體區域的不規則三角網和泰森多邊形進行存儲，當地塊發生變換時，水源覆蓋范圍不變，因此只需要再次將地塊與該泰森多邊形進行空間求交即可獲得該地塊最臨近的水源。

如前所述，傳統搜索方法必須逐點進行距離或空間判定，按照一個縣域10萬地塊，水源 1 000個計算，運算次數在一億次以上；而采用該方法，提取中心點、構建泰森多邊形、空間分析共計 3 000次運算即可完成，時間節約及效率提升非常明顯。以某市二次土地調查圖版為例，數據量約10萬個圖斑，水源數量約0.14萬。傳統方法耗費超過半小時，新方法僅需要 4 min。而且一旦數據出錯，該方法在原有中間數據的基礎上幾分鐘即可完成修正搜索，這是傳統方法必須重新計算所不可比擬的。

4 結 語

本文闡述的最臨近服務點的搜索方法采用不規則三角網與泰森多邊形的結合，簡單方便地實現興趣點周圍最臨近服務點的搜索。優選用于與位置服務相關的最近搜索，興趣點可以是如居民區之類，服務點可以是超市、醫院等。并且通過服務點覆蓋范圍模式反向搜索范圍內興趣點的方式，可將第一次搜索構建的泰森多邊形作為中間數據存儲，當興趣點發生變動時，僅需將變化的興趣點與該泰森多邊形進行空間求交即可得到所需的最臨近服務點，使得搜索一次數據可以多次使用，大大減少了運算量。再者當服務點發生變化時，也僅對該服務點的周邊服務點構成影響，只需重新構建新變動服務點附近的泰森多邊形，即可完成該泰森多邊形的更新，運算量也得到相應減少。

不足之處在于，服務點的服務能力各異，筆者籠統認為其服務能力一致，與實際生產存在差異。再者文中考慮的是重心在對應多邊形內的情況，對于不滿足條件的情況，需要人工干預。此外該服務區分析基于簡單的幾何距離，未考慮道路通達性和道路實際距離，因此該方法在宏觀服務能力分析方面具有一定的優勢同時也存在數據計算偏差的問題，這也是該方法在應用時必須注意的地方。