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

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

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

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

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