邊界標記在註解系統之應用

Boundary Label Placement and Its Application to Text Annotation

吳湘筠(Hsiang-Yun Wu)

指導教授 ： 顏嗣鈞

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.02864

摘要

在資訊視覺化的研究領域，邊界標記被應用在許多不同的地方。一種常見的邊界標記形式包含一個定點及其對應的一個標籤，且這個標籤被放置在整個地圖的外圍上。在某些邊界標記應用領域，被標示的定點可能會分成多個群組連接到一個標籤或者一個定點連接至多個標籤亦或者多對多的情況，在這?塈畯怜Q論的是一對一的情況。 在這篇論文裡，我們討論如何使用邊界標記法來改進Microsoft Office Word的註解系統。我們提供一個多項式時間的演算法來解決單一邊界的註解系統，此時可以藉由連結線段的彎曲來做視覺上的改進。我們也討論如何在雙邊標記上，平均最小化標籤的高度以及最小化連結線段的長度，也就是說，這個問題的目的是為了找出一個好的標籤排列方法，使得標籤高度最小，而連結線段的長度也最短。我們採用的連結線段的方式是垂直-平行-垂直(由零條或兩條垂直線段跟一條水平線段所組成)連結邊界的方式，而這個問題具有NP-complete的複雜度。因此，我們採用了在計算數學中用於解決最優化的搜索演算法遺傳演算法來解決這個問題。在這篇論文裡的所提及的問題，我們假設連結線段是連接在標籤的正中間，換句話說，也就是擁有固定的連接點。這個雙邊界標記的問題是標籤配置和圖形繪製的綜合體，是個有趣且值得探討的問題。

關鍵字

邊界標記 ； 文章註解 ； 圖學 ； 地圖標記 ； 資訊視覺化

並列摘要

Boundary labeling which can be found in many applications is an important field of information visualization. A conventional boundary labeling scheme connects one site to a unique label placed on the boundary of the drawing. In certain applications of boundary labeling, however, sites may be grouped or separated into more than one group and connect to an identical label on a picture or in an article with abundant numbers of sites and labels. We consider a special formula which includes one site and one identical label here.
In this thesis, we try to improve the annotation system of Microsoft Office Word by using boundary labeling solving methods. We provide a polynomial time solution to solve one-side annotation while the leader can be wound, and rerouted to improve the visualization. We also consider the label height minimization problem and leader length minimization for two-side boundary labeling of the annotation system, i.e. the problem of finding a good leader and label placement, such that the number of total label height and total leader length is minimized. We proved that the two-side labeling problem for type-opo leaders (rectilinear lines with either zero or orthogonal segment and one parallel segment) is NP-complete. Then, we give a heuristic genetic algorithm and analyze its properties for the problems. For all the problems in this thesis, we assume that the connecting label ports are fixed ports, i.e. the point where each leader is connected to the label is fixed.
These problems are interesting in that it is a mixture of a label-placement and a graph-drawing problem.

並列關鍵字

boundary labeling ； text annotation ； graph drawing ； map labeling ； information visualization

參考文獻

[3] M. Bekos, M. Kaufmann, A. Symvonis, and A. Wolff. Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps. Proc. of the 12th Int. Symposium on Graph Drawing (GD’04), pp. 49-59, 2004.

[8] M. Formann, F. Wagner, A Packing Problem with Applications to Lettering of Maps, in: Proc. 7th Annual ACM Symposium on Computational Geometry (SoCG’91), 1991, pp. 281–288.

[10] S.A. Hirsch, An Algorithm for Automatic Name Placement Around Point Data, The American Cartographer 9 (1) (1982) 5–17.

[11] E. Imhof. Positioning Names on Maps. The American Cartographer, vol.2, pp. 128-144, 1975.

[16] S. Zoraster, Practical Results using Simulated Annealing for Point Feature Label Placement, Cartography and GIS 24 (4) (1997) 228–238.