多目的地地圖的簡(jiǎn)化及布局優(yōu)化方法研究.pdf

1、多目的地地圖作為一種導(dǎo)航地圖，能夠指引某個(gè)區(qū)域內(nèi)的用戶到達(dá)多個(gè)目的地。多目的地地圖常見于旅游景區(qū)，為游客游覽多個(gè)景點(diǎn)提供導(dǎo)航。它也常被印刷在商家的宣傳材料中，以告知周圍的顧客如何快速達(dá)到商家的地址。使用現(xiàn)有的在線地圖服務(wù)（谷歌地圖、百度地圖等）來自動(dòng)生成多目的地地圖往往存在許多缺陷，如存在冗余數(shù)據(jù)和無法靜態(tài)顯示不同層次的細(xì)節(jié)信息。當(dāng)前多目的地地圖的制作主要由專業(yè)的制圖人員手工去繪制完成，他們需要依靠自身豐富的經(jīng)驗(yàn)對(duì)地圖數(shù)據(jù)進(jìn)行簡(jiǎn)化，然后

2、運(yùn)用大量的制圖設(shè)計(jì)規(guī)則包括變形、簡(jiǎn)化和抽象等布局技術(shù)來增強(qiáng)地圖的可讀性，這是一個(gè)非常費(fèi)時(shí)費(fèi)工的過程。因此，自動(dòng)地簡(jiǎn)化地圖數(shù)據(jù)和實(shí)現(xiàn)多目的地地圖布局優(yōu)化是一項(xiàng)具有挑戰(zhàn)性的工作。
　　本文提出了一種基于設(shè)計(jì)規(guī)則的地圖數(shù)據(jù)簡(jiǎn)化算法。首先，通過分析認(rèn)知心理學(xué)家的有關(guān)研究成果和手繪制圖專家的設(shè)計(jì)經(jīng)驗(yàn)，我們從中歸納總結(jié)出簡(jiǎn)化和設(shè)計(jì)多目的地地圖的規(guī)則。這些規(guī)則指導(dǎo)系統(tǒng)根據(jù)用戶的個(gè)性化需求，從大量的原始地圖數(shù)據(jù)中抽取與當(dāng)前用戶最相關(guān)的信息，忽略無

3、關(guān)信息。然后，結(jié)合設(shè)計(jì)規(guī)則構(gòu)建出分層次的地圖數(shù)據(jù)簡(jiǎn)化算法，依次識(shí)別路網(wǎng)中類型為高速公路、主干道和街道的“可見環(huán)”，環(huán)上的關(guān)鍵點(diǎn)與目的地之間使用A*算法尋找最佳線路進(jìn)行連接，構(gòu)建簡(jiǎn)化的稀疏地圖網(wǎng)絡(luò)。其中，最佳線路被定義為距離最短、轉(zhuǎn)彎最少和冗余最少的線路。最后，在維持路網(wǎng)正確拓?fù)浣Y(jié)構(gòu)的前提下，使用Douglas-Peucker算法去除道路上冗余的數(shù)據(jù)點(diǎn)。
　　在地圖數(shù)據(jù)簡(jiǎn)化的基礎(chǔ)上，本文提出了一種多目的地地圖布局優(yōu)化模型，它使用包含

4、目的地的矩形關(guān)注區(qū)域(ROI)的空間位置關(guān)系，以及連接它們的連接邊來描述多目的地地圖的布局。首先，本文使用改進(jìn)的Min-Cut算法將地圖切割為多個(gè)ROI，確保每個(gè)ROI僅包含一個(gè)目的地，擁有完整的可達(dá)線路，最少的重疊面積等。然后，依據(jù)地圖設(shè)計(jì)規(guī)劃將地圖布局優(yōu)化問題形式化為一個(gè)約束系統(tǒng)，約束條件包括充分利用顯示空間、限制道路的長(zhǎng)度、角度和維持道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)等。最后，我們使用基于擾動(dòng)的模擬退火算法從復(fù)雜的布局空間中求解出滿足該約束系統(tǒng)的