一種變比例尺地圖的導航算法

劉琰翔，陳子恬，陳俊熙

（華南師范大學計算機學院，廣州　510631）

一種變比例尺地圖的導航算法

劉琰翔，陳子恬，陳俊熙

（華南師范大學計算機學院，廣州510631）

0　引言

變比例尺地圖在日常生活十分常見，包括旅游地圖、宣傳材料和手繪地圖等。這種地圖不講求準確性，通常強調重要建筑物和區域而省略其他的東西，并且在同一張地圖中，所強調區域的比例尺可能會比其他區域大，以至整個圖面的不同部分具有不同的比例尺。所以，地圖往往是失真的，不能精確地反映各點的實際位置以及各條路徑的實際方位和長度。這類地圖是適合人們使用的，但它們并不適合用于導航，因為失真和無法估量的不準確性使地理編碼和定位變得十分困難，無法作為基礎地圖簡單地應用于傳統的電子導航系統中。但是這種繪制靈活的變比例尺地圖又比現今電子導航系統使用的等比例尺地圖更明了生動，同時符合使用和審美的需求。

為了使這種靈活生動的變比例尺地圖也能用于智能移動終端的電子導航系統中，本文提供了一種變比例尺地圖導航算法來實現在這種變比例地圖上定位。這種算法是使失真的變比例尺地圖與智能手機上的定位功能相結合的關鍵技術。

1　相關工作

國內對于變比例尺地圖的投影及可視化研究深入［1～3］，但在變比例尺地圖導航這個領域很少有人研究。國際上，日本對此研究很多［4～6］，其中東京大學的幾位學者提出了一種變比例尺導航的思想［4］。本文在此基礎上，對算法進行改進并實現。

2　導航算法

本算法流程見圖1，共有兩個階段：坐標轉換和誤差減免。

圖1　導航算法流程圖

首先，定義導航地圖上的任意一點為p。

這里的c=（x，y）是地圖上的像素坐標；l=（longitude，latitude）是地理坐標；因此，一張地圖可以表示成如下形式：

通過手機或平板的GPS功能得到當前位置的l= （longitude，latitude），而需要得到的是該點在地圖上的坐標c=（x，y）。首先必須存在足夠多的參考點，而這些參考點的地理坐標和地圖坐標都已經得知。然后，假設需要得知一點pm的地圖坐標，首先就需要根據pm的地理坐標找到參考點中離它最近的兩個坐標pm1和pm2。很明顯，△cmcm1cm2和△lmlm1lm2是相似的（由于地球是個球體，所以△lmlm1lm2實際上是曲面三角形，但是因為各點之間的距離十分近，所以可以認為是一個平面三角形）。滿足以下式子：

所以根據相似變換可以得到dist（lm，lm1），到dist（lm，lm2）和到dist（lm1，lm2）的距離，而lm1，lm2的坐標已經知曉。所以，問題就轉變為兩圓相交求相交點坐標了，如圖2。由△cmkcm1和cmkcm2可以得到：

圖2　兩圓相交圖

由d=a+b可以得到：

而cm1kcm2在同一直線上，所以有：

由此，便可以確定 cm=（xm，ym），該點就可以在等比例尺的地圖上無偏差地轉換坐標系。

自然，以上算法只能用于等比例尺地圖的轉換，簡單方便且不需要太多參考點，但用在變比例尺地圖上會出現如下誤差：

（1）單方面伸縮誤差

如圖3所示，圖3（A）是正常比例的圖，而圖3（B）拉伸了40%，圖3（C）縮小了40%，根據該地圖，點P在伸展后的地圖對應的點應該是Pa，但是根據上面的算法得到的結果卻會落在Pb。對于這種誤差，實驗發現如果游客和路線是在同一路徑上的話，這種誤差是可以接受的。所以在選取參考點的時候也需要盡量選取同一直線的參考點。

圖3　單方面伸縮誤差

（2）比例尺不同誤差

如圖4所示，圖4（A）是正常尺度，而圖4（B）為非常規尺度，圖（B）放大了A點，縮小了B點，使得A點和B點的地圖坐標發生改變，從而影響到了點P的定位。根據地圖，正確的點P在變比例地圖下應該落在Pa，而實際算法所得卻得到Pb。

圖4　比例尺不同引起的誤差

（3）誤差減免

對于不規則的地圖，由于無法估量不同地圖的失真，至今還沒有一個統一的算法可以完全消除誤差。然而，誤差雖然無法完全免除，但本文提出一些方法可以進行減免。

主要改進如下：

①在選取參考點時，選取同一區域內的以待測點P為原點的不同象限內的三個坐標，并兩兩分別拿來確定P點坐標，然后將三次得到的坐標的平均值作為P點的地圖坐標。

②去除奇異點。在每次坐標換算時，得到地圖一點的坐標時，若與上一點坐標距離相差太大，則拋棄該點。

③在合理的地方設置更多的參考點。首先，景點坐標的設置應該設在各個景點的門口而非中間。另外，在導航過程中，用戶基本上會沿著路徑走，所以應該在主干路上設置更多的參考點，并且在道路的交叉路口和拐角處設置參考點。這些點多設置在景點密度不夠大的區域。

④將地圖分區域，加快查詢參考點的效率。每次選參考點時都先將當前坐標與當前區域的中心點坐標進行比較，確定當前點落在當前區域的第幾象限，然后將區域中心點換成該象限的中心點，一直進行此操作，直至區域足夠小。

3　測試數據

以華師校園為例，在同一區域內測試參考點對坐標轉換偏差距離的影響。

在同一區域內，在距離和位置合理的情況下，測試在同一點采取三個不同位置的參考點方案下與實際距離的偏差程度，然后再在不同地點測試，求平均值。

測試結果如表1所示。

表1　參考點對導航的影響

在同一區域內，在位置和數量合理的情況下，測試在同一點采取三個不同參考點距離的方案下與實際距離的偏差程度，然后再在不同地點測試，求平均值。測試結果如圖5。

經測試發現，當合理參考點距離當前位置30米內時，導航誤差是可以接受的。

在同一區域內，在距離和位置合理的情況下，測試在同一點采取三個不同參考點數量的方案下與實際距離的偏差程度，然后再在不同地點測試，求平均值。測試結果如圖6。

測試發現，在半徑50米的區域內當合理的參考點數量達到5個時，偏差程度便可以接受。

4　結語

為了解決傳統導航在變比例尺地圖上的無能為力，以及更好適應大眾對于地圖的需求，本文提出了一種能在變比例尺地圖上導航的算法，并且從參考點位置、參考點距離和參考點數量三個方面對該算法進行測試。實驗表明，在半徑50米的區域內存在5個以上的參考點時，導航誤差可以接受。另外，若存在3個相對于當前位置不同側的參考點，導航效果更佳。

［1］閆超德，郭王，白建軍，趙姍，武舫，賀添.變比例尺地圖制圖方法評述［J］.測繪科學，2014（3）：34～36

［2］李連營，司若辰，許小蘭，李敏.基于地圖投影思想的地圖變比例尺可視化［J］.地理空間信息，2012（5）：161～163

［3］高平，馮嚴.導航點滴地圖的多比例尺可視化的實現［J］.江西測繪，2010（4）：35～37

［4］Min Lu，Masatoshi Arikawa，Location-Based Illustration Mapping Applications and Editing Tools［J］.Cartographica.2013（48）：100-112

［5］Hideki Kaji，Masatoshi Arikawa.Personal Location Based Services on Place-enhanced Blog［J］.ACM Multimedia.2008（10）：917-920

［6］Min Lu，Masatoshi Arikawa.Map-Based Storytelling Tool for Real-World Walking Tour［J］.Progress in Location-Based Services.2013 （1）：435-451

圖5　參考點距離對導航的影響

圖6　參考點數量對導航的影響

Variable Scale Map；Coordinate Transformation；Deviation Reduction

Variable Scale Map Navigation Algorithm

LIU Yan-xiang，CHEN Zi-tian，CHEN Jun-xi
（College of Computer Science，South China Normal University，Guangzhou 510631）

1007-1423（2015）17-0014-04

10.3969/j.issn.1007-1423.2015.17.003

劉琰翔（1993-），男，廣東揭陽人，本科，研究方向為算法設計與分析

陳子恬（1993-），女，廣東汕頭人，本科，研究方向為算法設計與分析

陳俊熙（1993-），男，廣東云浮人，本科，研究方向為算法設計與分析

2015-04-03

2015-05-13

導航是目前基于位置的服務中尤為常見的一種服務。傳統的導航服務應用于車輛駕駛和人們出行，而旅游業的發展對地圖提出新的要求，也使得傳統的導航服務不再適用。針對這種情況，提出一種可以應用于變比例尺地圖上的導航算法。該算法的主要思想是坐標轉換和誤差減免。實驗表明，該算法在變比例尺地圖上誤差小，能有效導航。

變比例尺地圖；坐標轉換；誤差減免

Navigation is particularly common in location based service.The traditional navigation is used to driving and travel.The development of the tourism industry puts forward new requirements on the map，which makes the traditional navigation service is no longer applicable. Proposes a kind of navigation algorithm which can be used on the variable scale map.The main idea of the algorithm is the coordinate conversion and deviation reduction.The results show that the algorithm has little deviation on the variable scale map，and it can effectively navigate.