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

魏金占，易桂軒

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

1 引 言

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

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

2 解決思路

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

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

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

3 實施案例

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

本文以超圖地理信息系統(tǒng)為實現(xiàn)平臺，具體步驟為：

(1)完整性檢查，將水源面狀數(shù)據(jù)轉(zhuǎn)換為點狀數(shù)據(jù)并記錄對應(yīng)的屬性信息；

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

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

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

③將地塊范圍面狀數(shù)據(jù)轉(zhuǎn)換為地塊中心點數(shù)據(jù)，得到地塊點并記錄該地塊的屬性信息；

(2)基于各個水源中心點構(gòu)建不規(guī)則三角網(wǎng)；

將各個水源中心點構(gòu)建不規(guī)則三角網(wǎng)，確定區(qū)域內(nèi)水源覆蓋范圍，確保每處水源被三角網(wǎng)覆蓋，如圖2所示；

圖2 構(gòu)建的不規(guī)則三角網(wǎng)

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

以不規(guī)則三角網(wǎng)為準(zhǔn)構(gòu)建泰森多邊形，將整體區(qū)域劃分為多個子區(qū)域，各個水源中心點分別位于對應(yīng)的子區(qū)域中，該子區(qū)域即為對應(yīng)水源的服務(wù)范圍。

(4)求解最鄰近水源

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

圖3 地塊1位于水源Ⅰ對應(yīng)的子區(qū)域，則地塊最臨近的水源為水源Ⅰ

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

將該整體區(qū)域的不規(guī)則三角網(wǎng)和泰森多邊形進(jìn)行存儲，當(dāng)?shù)貕K發(fā)生變換時，水源覆蓋范圍不變，因此只需要再次將地塊與該泰森多邊形進(jìn)行空間求交即可獲得該地塊最臨近的水源。

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

4 結(jié) 語

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

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