透過您的圖書館登入
IP:3.236.57.1
  • 學位論文

帶有兩或三個叉子齒指引線的多重堆疊邊界標記

Multi-stack Boundary Labeling with Two or Three Prong Leaders

指導教授 : 潘雙洪
若您是本文的作者,可授權文章由華藝線上圖書館中協助推廣。

摘要


Boundary labeling deals with labeling point of interest in a visually improved way. We assume that the features that we want to label can b e represented by points, line segments or simple close polygons. The features are inscribed in an axis parallel rectangle R with no two features sharing the same x or y-coordinate. Labels are placed at the boundary of the axis parallel rectangle in its 2^n sides where 0 ≤ n ≤ 2. These labels will contain textual information that will describe the features. We want labels that do not overlap and are large enough to be readable. Even simple formulations of this problem are NP-complete. In this thesis, our objective is to minimize the total leader length and the total number of leader crossings. Our main result is a polynomial time algorithm for crossing-free labeling. We use a sweep line algorithm and dynamic programming to meet our objectives. In the algorithm three points will be attached to one horizontal line which runs from the left side of the label to vertically top or bottom of the x−coordinate of the minimum of the three points. Then vertical lines called prong attach each of the point to the horizontal. In theory in order to have a good looking labeling, we make the points to be a multiples of three. Likewise if two points per line are used, we make sure the points are even numbers. If three points are labeled at a time we use three stack at the boundary of R likewise for two points, we use two stacks. We also analyzed the NP completeness of this boundary labeling problem.

關鍵字

連接線 標籤 正交 地圖 NPC

並列摘要


無資料

並列關鍵字

Leader Label Prong Orthogonal map NP-complete

參考文獻


[1] M. Bekos, M. Kaufmann, M. Nollenburg, and A. Symvonis. Boundary labeling with octilinear leaders. Algorithmica, pages 57:436–461, 2010.
[7] M. A. Bekos, M. Kaufmann, A. Symvonis, and A. Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. pages 49–59, 2004.
[9] A. Gemsa, J. H. Haunert, and M. Nollenburg. Boundary labeling algorithms for panorama images. In GIS, pages 289–298, 2011.
[11] M. Kaufmann. On map labeling with leaders. In Efficient Algorithms, pages 290–304, 2009.
[13] C. C. Lin. Crossing-free many-to-one boundary labeling with hyperleaders. In Proc. of 3rd IEEE Pacific Visualization Symposium (Pacific Vis.2010), IEEE Press:185–192, 2010.

延伸閱讀