張 偉，于 靜，陳儒敏，張鴻博

（北京科技大學(xué)天津?qū)W院信息工程系，天津 301830）

關(guān)鍵字：便攜定位裝置、逆地理編碼算法、傳統(tǒng)搜索算法、k-d樹算法

0 引言

當(dāng)前，隨著移動互聯(lián)網(wǎng)基建設(shè)施的逐步完善和智能手機、平板等終端設(shè)備的普及，基于智能終端的APP 應(yīng)用程序獲得爆發(fā)式增長，其中絕大部分業(yè)務(wù)都需要使用設(shè)備的地理位置信息。同時，由于國內(nèi)經(jīng)濟的發(fā)展和人民生活水平的提升，私家車駕車出行的比例大幅上升。駕駛員普遍應(yīng)用高德地圖、騰訊地圖等移動導(dǎo)航APP 軟件。通過使用此類軟件，司機往往能夠快速知曉車輛所處具體位置，獲得其經(jīng)緯度坐標(biāo)，并能夠進行路徑規(guī)劃等高級操作。

然而，這類應(yīng)用有一個弊端，即必須在聯(lián)網(wǎng)的情況下才能使用。目前，在我國通訊基站實施覆蓋的平原城市、鄉(xiāng)村等地區(qū)，實時使用此類軟件的問題不大；但在突發(fā)或者特定情況下，通信網(wǎng)絡(luò)的獲取比較困難：比如，在地質(zhì)勘探工作者進入深山和原始森林進行科學(xué)考察時，或者突發(fā)地質(zhì)氣象災(zāi)害時，由于不具備通訊基站等通訊設(shè)施，這類導(dǎo)航軟件往往不能正常使用。

針對這類無網(wǎng)絡(luò)情況下的定位需求，本文提出了一種基于k-d 樹的逆地理編碼算法，此算法應(yīng)用場景定位于便攜式離線定位裝置上。同時，編寫基于歐氏距離和半正矢公式的兩種傳統(tǒng)搜索算法代碼，作為對照組。通過測試，不僅驗證了k-d 樹算法的正確性，而且證明在較大測試集的情況下，此算法運行效率比傳統(tǒng)算法高出近300倍。

1 逆地理編碼算法的研究現(xiàn)狀

逆地理編碼算法，亦稱反地理編碼算法，或地址解析算法，是指從已知的經(jīng)緯度坐標(biāo)推算出對應(yīng)的地址描述的轉(zhuǎn)換算法。一般用于根據(jù)定位點經(jīng)緯度來獲取該處的位置詳細(xì)信息，在地質(zhì)考察、野生動物保護、軍事等領(lǐng)域有著大量的應(yīng)用場景。目前，大部分系統(tǒng)和項目開發(fā)中，逆地理編碼算法都是通過調(diào)用互聯(lián)網(wǎng)廠商提供的逆地理編碼服務(wù)接口來實現(xiàn)的。國內(nèi)市場占有率較高的廠商，例如百度地圖和高德地圖，均推出了基于開放地圖服務(wù)的地圖API接口。文獻［1］中詳細(xì)闡述了如何通過編寫JavaScript 腳本程序調(diào)用高德開放地圖接口，輸入經(jīng)緯度得出地理信息的過程。國外的諸多網(wǎng)站，如PickPoint、GeoNames、MapQuest等服務(wù)商也提供類似的服務(wù)。

然而，在上述提到的某些應(yīng)用場景中，離線逆地理編碼算法的實現(xiàn)又是不可回避的要求。目前，國內(nèi)外對逆地理編碼具體算法實現(xiàn)及流程的研究很少，大多數(shù)只是調(diào)用現(xiàn)成的程序接口或者封裝好的模塊。高德集團的一份專利中，提及了離線的逆地理編碼的方法及其裝置，不過其側(cè)重于設(shè)備端的功能設(shè)計及實現(xiàn)，對具體的算法實現(xiàn)流程并未進行深入的闡釋，可參考價值有限。文獻［3］提出了一種基于GeoHash算法的分層調(diào)度方法和區(qū)間調(diào)度模型，可對共享單車的調(diào)度方案進行有效地規(guī)劃，通過對比已有的分層調(diào)度方案，得出了算法收斂速度快、模型時間復(fù)雜度低的結(jié)論。但是，該文章直接調(diào)用封裝好的第三方GeoHash計算模塊，未對其實現(xiàn)機理做詳細(xì)研究。針對上述不足，本文將逐步通過問題分析、測試集收集、測試組/對比組代碼測試等流程來研究這一問題。

2 問題的分析

離線逆地理編碼算法的流程，簡單來說，即是在未聯(lián)網(wǎng)的情況下，從便攜式離線定位裝置的GPS 接收器獲取一個或多個經(jīng)緯度數(shù)據(jù)，再由算法與內(nèi)置數(shù)據(jù)集進行搜索和比對，得出距離所測數(shù)據(jù)點最近的內(nèi)置地址數(shù)據(jù)，然后將結(jié)果數(shù)據(jù)以地理名稱的字符串形式返回。該計算流程涉及兩方面關(guān)鍵問題，即：①內(nèi)置數(shù)據(jù)集的來源、數(shù)據(jù)格式和參考點位的數(shù)量級；②搜索算法的計算效率和正確性。下文將逐一進行簡述。

2.1 內(nèi)置數(shù)據(jù)集

本文算法的應(yīng)用范圍先限定為國內(nèi)區(qū)域，數(shù)據(jù)集采用國家標(biāo)準(zhǔn)行政地理區(qū)劃中的國內(nèi)行政區(qū)劃不同粒度范圍地名劃分機制，具體信息如表1 所示。

表1 國內(nèi)行政區(qū)劃分級劃分機制

根據(jù)表1定義本文所用的地址數(shù)據(jù)結(jié)構(gòu)，如表2所示。

表2 地址數(shù)據(jù)結(jié)構(gòu)

其中，scale_int 取值范圍為1～6，表征該條數(shù)據(jù)的地址級別；lon_f、lat_f，使用浮點數(shù)記錄地址的經(jīng)緯度信息；add_1～add_6，記錄地址要素的字符串，比如add_3取值街道名稱，上限為256個字符。

本文的數(shù)據(jù)集取自國家統(tǒng)計局2020 年公布的數(shù)據(jù)，分別獲取3/4/5 級行政區(qū)劃數(shù)據(jù)用于后續(xù)測試。經(jīng)過清洗后的數(shù)據(jù)個數(shù)如下：3級數(shù)據(jù)3552 個，4 級 數(shù) 據(jù)42358 個，5 級 數(shù) 據(jù)758050個。從3 級數(shù)據(jù)中隨機抽取296 個作為測試數(shù)據(jù)，以便驗證算法的正確性。因此，3級行政區(qū)劃數(shù)據(jù)用于內(nèi)置數(shù)據(jù)集的個數(shù)變?yōu)?256 個。下文中，主要應(yīng)用3 級行政數(shù)據(jù)驗證算法的正確性，4級、5級行政數(shù)據(jù)測試算法的執(zhí)行效率。

2.2 基于經(jīng)緯度數(shù)據(jù)的距離計算

在計算給定坐標(biāo)點具體屬于哪個地理區(qū)劃時，最直接的辦法是計算此點與內(nèi)置數(shù)據(jù)集全部參考數(shù)據(jù)點的距離，并排序選出最小的點，以此作為所屬地理區(qū)塊劃分。當(dāng)然，考慮到行政區(qū)劃邊界不是嚴(yán)格的與經(jīng)緯線平行的直線，還需要綜合附近多點的計算結(jié)果進行判斷。本文將問題簡化，以距離計算為基本算法進行逆地理編碼研究。

圖1 中，點是已知點，點是所求點，點是地球球心，、兩點間的弧線表示球面距離。

圖1 球面兩點間距離計算示意圖

計算距離的算法有多種，一為歐拉公式（Euclidean Distance），計算與點的直線距離，如公式（1）所示。

考慮到地球是個球面，第二種采用半正矢公式（Haversine Formula）計算球面上兩點間的距離，推導(dǎo)過程如下所示。

對于球面上任意兩點，圓心角的半正矢值（）可用公式（2）進行計算。

公式（2）中，代表弧度制圓心角；代表地球半徑，取值6378 千米；(lon,lat) 和(lon,lat)分別代表球面上任意兩點和的弧度制經(jīng)緯度坐標(biāo)，其值采用WGS 84 標(biāo)準(zhǔn)GPS 坐標(biāo)，取自便攜式裝置中的GPS 定位模塊。半正矢公式hav（）的具體計算過程見公式（3）。

將公式（3）帶入公式（2）第二個等號右邊式子，得到公式（4）。

反半正矢函數(shù)的計算公式如公式（5）所示。

將公式（4）和公式（5）聯(lián)立，得出距離的計算公式如下。

3 兩種傳統(tǒng)搜索算法

本文采用的傳統(tǒng)搜索算法主要通過計算測試點與內(nèi)置數(shù)據(jù)集各點的距離，選擇數(shù)值最小的點作為輸出結(jié)果。為了加快搜索速度，將經(jīng)過Euclidean 或Haversine 公式計算后的距離集合進行排序，比較大小時采用傳統(tǒng)的二分法進行搜索。詳細(xì)步驟如下：

（1）算法初始化，將測試數(shù)據(jù)與內(nèi)置數(shù)據(jù)集讀入內(nèi)存；

（2）利用Euclidean 或Haversine 公式計算內(nèi)置數(shù)據(jù)集各點與測試數(shù)據(jù)間的距離，得到距離集合并排序；

（3）采用二分法搜索距離最小的點；

（4）結(jié)果返回對應(yīng)內(nèi)置數(shù)據(jù)集，輸出地址字符串；

（5）算法結(jié)束。

應(yīng)用5級行政區(qū)劃數(shù)據(jù)進行測試。為排除計算過程中的隨機影響，每次重復(fù)運行100次，取平均計算結(jié)果作為記錄值。表3 中，傳統(tǒng)1 和傳統(tǒng)2 分別對應(yīng)Euclidean 和Haversine 計算公式。傳統(tǒng)1 代表采用Euclidean 公式計算單次運行時間，傳統(tǒng)2 代表采用Haversine 公式計算方法單次運行時間。

表3 傳統(tǒng)算法在不同行政級別數(shù)據(jù)集情況下的計算情況

從表3可以看出，整體來看，隨著內(nèi)置數(shù)據(jù)集的增大，兩種傳統(tǒng)算法的單次計算運行時間逐漸增長。分別來看，采用Euclidean 公式的執(zhí)行時間稍短，但是正確率低于采用Haversine 公式的傳統(tǒng)2 算法。經(jīng)手動排查后，發(fā)現(xiàn)傳統(tǒng)1 算法判斷失誤的測試點與相鄰最近的內(nèi)置數(shù)據(jù)集點間距離較遠(yuǎn)，歐拉直線距離與球體表面的圓弧距離相對誤差較大?？偟膩碚f，采用傳統(tǒng)算法執(zhí)行效率比較低，單個測試點的查詢時間在4秒鐘以上，因此在多數(shù)場景應(yīng)用中是無法滿足時效要求的。鑒于采用Haversine 公式的正確率較高，故選其作為下文的對照組算法。

4 K-d樹算法的實現(xiàn)

k-d 樹，即k-dimensional tree，常用作空間劃分及近鄰搜索算法，是二叉空間劃分樹的一個特例。通常，對于維度為、數(shù)據(jù)點數(shù)為N 的數(shù)據(jù)集，k-d 樹適用于?2的情形。以采用3級行政區(qū)劃做內(nèi)置測試集為例，維度=2，數(shù)據(jù)點數(shù)=3256，滿足3256?4 的應(yīng)用條件。k-d 樹算法可以分為兩部分，一是為構(gòu)建k-d 樹本身這種數(shù)據(jù)結(jié)構(gòu)而建立的算法，即如何把包含大量數(shù)據(jù)的內(nèi)置數(shù)據(jù)集構(gòu)建成一棵k-d 樹；二是如何在建立的k-d 樹上進行最鄰近查找的算法，即查找k-d樹上距離測試數(shù)據(jù)最近的節(jié)點。

構(gòu)建內(nèi)測數(shù)據(jù)集經(jīng)緯度的k-d 樹算法簡述如下：循環(huán)依序取數(shù)據(jù)點的經(jīng)緯度數(shù)據(jù)作為切分維度，分別取數(shù)據(jù)點在該維度的經(jīng)緯度中值作為切分超平面，將中值左、右側(cè)的數(shù)據(jù)點分別掛在其左子樹和右子樹。遞歸處理其子樹，直至所有數(shù)據(jù)點掛載完畢。下面以3級行政區(qū)劃數(shù)據(jù)集中的甲～庚共7個數(shù)據(jù)點為例，只保留其1級行政區(qū)劃名稱及經(jīng)緯度數(shù)據(jù)；目標(biāo)數(shù)據(jù)點是地處河北省石家莊市橋西區(qū)的新百廣場商業(yè)綜合體。具體數(shù)據(jù)見表4。

表4 簡化k-d樹算法所需數(shù)據(jù)點

具體步驟如下：

（1）構(gòu)建根節(jié)點時切分維度為緯度，上述7個數(shù)據(jù)點按緯度從小到大進行排序，取中值乙點天津（39.14393，117.21081）為根節(jié)點；

（2）石家莊、邯鄲、邢臺三點在根節(jié)點的左半子樹，北京、唐山、秦皇島三點在根節(jié)點的右半子樹；

（3）構(gòu)建根節(jié)點的左子樹時，切分維度為經(jīng)度，中值點邢臺（37.06953，114.52048）作為分割平面，邯鄲為左子葉、石家莊為右子葉；

（4）根節(jié)點的右子樹構(gòu)建方法如上。

至此，k-d 樹構(gòu)建完成，如圖2 所示。圖中，每個數(shù)據(jù)點上的“經(jīng)-N”或“緯-N”代表劃分樹或子葉時，以本點的經(jīng)緯度作為切分維度的劃分標(biāo)準(zhǔn)。

圖2 7個數(shù)據(jù)點k-d樹的構(gòu)建示意圖

上述構(gòu)建過程結(jié)合圖3，可以看出，構(gòu)建一個k-d 樹即是將一個二維平面逐步劃分的過程。分割所用的超平面即是各個數(shù)據(jù)點的某一維度值。圖3背景中的各條實線，即為分割所用的超平面，為方便辨識，經(jīng)度線用粗實線標(biāo)注，緯度線用細(xì)實線標(biāo)注。

圖3 k-d樹搜索算法的“回溯”計算示意圖

k-d樹的搜素算法步驟如下：

（1）首先對k-d 樹做深度遍歷，取出距離最近的點，以圖4標(biāo)注的①→②→③為確定的搜索方向；

（2）為了明確丙葉子節(jié)點是否為真正的最鄰近點，還需要進行“回溯”操作：具體為算法沿搜索路徑反向查找是否有距離查詢點更近的數(shù)據(jù)點；在圖4 中，即為反向從③→④→⑤的過程；

圖4 k-d樹搜索算法的實現(xiàn)

（3）“回溯”算法實現(xiàn)由圖3 所示，圖中的左下角實心五角星為需要查詢的目標(biāo)地址。圖3中的“經(jīng)-1/緯-3”分別為在丙點按經(jīng)度、在己點按緯度做分割用的兩個超平面。計算目標(biāo)地址與丙點間的距離，以目標(biāo)地址為圓心，距離為半徑做圓。可以看到，圓與丙點的上一節(jié)點（己點）所確定的“經(jīng)-1”存在交點，說明己點所在的左半樹需要被“回溯”計算，完成過程④。而唐山所處的整棵樹的右半樹，由于未與所做出的圓出現(xiàn)交點，故不需要被計算，圖中用陰影覆蓋以示區(qū)分。同理，二級回溯完成過程⑤。

（4）再比較己點、庚點和兩點與目標(biāo)點的具體距離，選出距離目標(biāo)點最短的那個點，k-d樹搜索算法完成。得出丙點是所查詢地址的結(jié)論，即新百廣場位置在石家莊。

（5）以上步驟演示的是需要進行“回溯”計算的情況。如圖3中右下方，虛線圓圈中的實心三角為目標(biāo)點的另外一種情況：當(dāng)目標(biāo)點與最近的內(nèi)置數(shù)據(jù)點之間所作的圓，與其他超平面無交點時，則不必進行“回溯”操作。

應(yīng)用上述的k-d 樹算法編寫測試程序，在其他軟硬件測試條件與第4節(jié)一致的情況下，得到的測試結(jié)果如圖5所示。圖中橫坐標(biāo)刻度值為log 值，測試集數(shù)量在第一個測試點為296 個，隨后每次增加10 倍，最后一個測試點的數(shù)量達(dá)到2.96*10個。折線圖每個點附近的數(shù)值代表其算法執(zhí)行時間。

圖5 k-d樹算法在5級行政區(qū)劃下的計算結(jié)果

在第一個測試點，同樣輸入296個測試數(shù)據(jù)和5 級行政數(shù)據(jù)的情況下，k-d 樹算法的執(zhí)行時間僅為5.213 秒，換算成單點計算時間為0.017611 秒，相比于表2 中的傳統(tǒng)2 算法4.851秒，算法效率提升了274.45 倍。同時，算法正確率達(dá)到100%。

5 結(jié)語

針對離線逆地理編碼算法的研究，本文首先采用兩種傳統(tǒng)搜索算法進行測試，并對由半正矢公式進行球面距離計算的過程進行詳細(xì)推導(dǎo)，通過計算得到了傳統(tǒng)算法時效性低的結(jié)論。然后，通過搭建7個數(shù)據(jù)點的簡單k-d 樹模型與算法演示，闡述了k-d 樹算法的基本原理與計算步驟。測試結(jié)果表明k-d 樹算法能夠大幅提高計算效率和準(zhǔn)確率。