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

劉琰翔，陳子恬，陳俊熙

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

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

劉琰翔，陳子恬，陳俊熙

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

0　引言

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

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

1　相關(guān)工作

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

2　導(dǎo)航算法

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

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

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

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

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

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

圖2　兩圓相交圖

由d=a+b可以得到：

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

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

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

（1）單方面伸縮誤差

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

圖3　單方面伸縮誤差

（2）比例尺不同誤差

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

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

（3）誤差減免

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

主要改進(jìn)如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

4　結(jié)語(yǔ)

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

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

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

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

圖6　參考點(diǎn)數(shù)量對(duì)導(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-），男，廣東揭陽(yáng)人，本科，研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析

陳子恬（1993-），女，廣東汕頭人，本科，研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析

陳俊熙（1993-），男，廣東云浮人，本科，研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析

2015-04-03

2015-05-13

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