動態軌跡地圖標籤之演算法設計

Abstract

傳統地圖演算法注重於對一靜態地圖設計標籤演算法，而動態地圖允許使用者將地圖旋轉、移動，使得傳統地圖演算法無法直接使用在動態地圖上。本論文中考慮了動態軌跡地圖的演算法設計。在給定的軌跡以及點集中，找出不互相重疊的自動標籤化的演算法。在地圖的一邊對地圖上的點集做標籤，找出不重疊且維持相對順序的標籤方法。在論文中我們對軌跡地圖建立起線性規劃模型，並且使用可滑動的標籤方法，使得標籤不須先固定位置，在以往的研究中，標籤是固定在某一個位置。為了提升效率，本論文也提出啟發式演算法來尋找對標籤在地圖右方的標籤方法。最後在論文中比較不同演算法之間的效率。

Traditional map labeling focuses on static maps. As dynamic maps allow the user to move or rotate the map, traditional map labeling algorithms cannot easily be extended to dynamic maps. In this thesis, we consider the design of algorithms for trajectory-based dynamic boundary labelling. The goal is to find an automatic method to label the points along a given trajectory of a map in the framework of boundary labeling. Given a trajectory and a set of points, the design is to connect points to non-overlapping labels on one side of the boundary of the map. In this thesis, we design an Integer Linear Programming (ILP) formulation, which allows sliding ports as opposed to fixed ports assumed in much of the previous work. To improve the efficiency, heuristic algorithms are also given. Finally, experimental results are used to illustrate the effectiveness of our design.