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

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

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

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

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