劉琰翔，陳子恬，陳俊熙

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

一種變比例尺地圖的導(dǎo)航算法

劉琰翔，陳子恬，陳俊熙

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

0　引言

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

為了使這種靈活生動的變比例尺地圖也能用于智能移動終端的電子導(dǎo)航系統(tǒng)中，本文提供了一種變比例尺地圖導(dǎo)航算法來實現(xiàn)在這種變比例地圖上定位。這種算法是使失真的變比例尺地圖與智能手機上的定位功能相結(jié)合的關(guān)鍵技術(shù)。

1　相關(guān)工作

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

2　導(dǎo)航算法

本算法流程見圖1，共有兩個階段：坐標(biāo)轉(zhuǎn)換和誤差減免。

圖1　導(dǎo)航算法流程圖

首先，定義導(dǎo)航地圖上的任意一點為p。

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

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

所以根據(jù)相似變換可以得到dist（lm，lm1），到dist（lm，lm2）和到dist（lm1，lm2）的距離，而lm1，lm2的坐標(biāo)已經(jīng)知曉。所以，問題就轉(zhuǎn)變?yōu)閮蓤A相交求相交點坐標(biāo)了，如圖2。由△cmkcm1和cmkcm2可以得到：

圖2　兩圓相交圖

由d=a+b可以得到：

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

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

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

（1）單方面伸縮誤差

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

圖3　單方面伸縮誤差

（2）比例尺不同誤差

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

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

（3）誤差減免

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

主要改進如下：

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

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

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

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

3　測試數(shù)據(jù)

以華師校園為例，在同一區(qū)域內(nèi)測試參考點對坐標(biāo)轉(zhuǎn)換偏差距離的影響。

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

測試結(jié)果如表1所示。

表1　參考點對導(dǎo)航的影響

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

經(jīng)測試發(fā)現(xiàn)，當(dāng)合理參考點距離當(dāng)前位置30米內(nèi)時，導(dǎo)航誤差是可以接受的。

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

測試發(fā)現(xiàn)，在半徑50米的區(qū)域內(nèi)當(dāng)合理的參考點數(shù)量達到5個時，偏差程度便可以接受。

4　結(jié)語

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

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

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

［3］高平，馮嚴(yán).導(dǎo)航點滴地圖的多比例尺可視化的實現(xiàn)［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　參考點距離對導(dǎo)航的影響

圖6　參考點數(shù)量對導(dǎo)航的影響

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-），男，廣東揭陽人，本科，研究方向為算法設(shè)計與分析

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

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

2015-04-03

2015-05-13

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

變比例尺地圖；坐標(biāo)轉(zhuǎn)換；誤差減免

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.