請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/71360完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 顏嗣鈞(Hsu-Chun Yen) | |
| dc.contributor.author | Ming-Hsien Wu | en |
| dc.contributor.author | 吳明憲 | zh_TW |
| dc.date.accessioned | 2021-06-17T05:59:22Z | - |
| dc.date.available | 2019-02-15 | |
| dc.date.copyright | 2019-02-15 | |
| dc.date.issued | 2019 | |
| dc.date.submitted | 2019-02-13 | |
| dc.identifier.citation | [1] Kamran Ali, Knut Hartmann, and Thomas Strothotte. Label layout for interactive 3d illustrations. Journal of WSCG, 13(1):1–8, 2005.
[2] Lukas Barth, Benjamin Niedermann, Martin Nöllenburg, and Darren Strash. Temporal map labeling: A new unified framework with experiments. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 23. ACM, 2016. [3] K. Been, E. Daiches, and C. Yap. Dynamic map labeling. IEEE Transactions on Visualization and Computer Graphics, 12(5):773–780, Sep. 2006. [4] Michael A Bekos, Michael Kaufmann, Martin Nöllenburg, and Antonios Symvonis. Boundary labeling with octilinear leaders. Algorithmica, 57(3):436–461, 2010. [5] Michael A Bekos, Michael Kaufmann, Katerina Potika, and Antonios Symvonis. Polygon labelling of minimum leader length. In Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation-Volume 60, pages 15–21. Australian Computer Society, Inc., 2006. [6] Michael A Bekos, Michael Kaufmann, Antonios Symvonis, and Alexander Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. Computational Geometry, 36(3):215–236, 2007. [7] Marc Benkert, Herman J Haverkort, Moritz Kroll, and Martin Nöllenburg. Algorithms for multi-criteria boundary labeling. J. Graph Algorithms Appl., 13(3):289–317, 2009. [8] Jean-Daniel Fekete and Catherine Plaisant. Excentric labeling: dynamic neighborhood labeling for data visualization. In Proceedings of the SIGCHI conference on Human Factors in Computing Systems, pages 512–519. ACM, 1999. [9] Martin Fink, Jan-Henrik Haunert, André Schulz, Joachim Spoerhase, and Alexander Wolff. Algorithms for labeling focus regions. IEEE Transactions on Visualization and Computer Graphics, 18(12):2583–2592, 2012. [10] Andreas Gemsa, Benjamin Niedermann, and Martin Nöllenburg. Trajectory-based dynamic map labeling. In International Symposium on Algorithms and Computation, pages 413–423. Springer, 2013. [11] Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter. Consistent labeling of rotating maps. Number 1, pages 308–331. Springer, 2016. [12] Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter. Evaluation of labeling strategies for rotating maps. Journal of Experimental Algorithmics (JEA), 21:1–4, 2016. [13] Jan-Henrik Haunert and Tobias Hermes. Labeling circular focus regions based on a tractable case of maximum weight independent set of rectangles. In Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Interacting with Maps, pages 15–21. ACM, 2014. [14] Niklas Heinsohn, Andreas Gerasch, and Michael Kaufmann. Boundary labeling methods for dynamic focus regions. In Visualization Symposium (PacificVis), 2014 IEEE Pacific, pages 243–247. IEEE, 2014. [15] Eduard Imhof. Positioning names on maps. The American Cartographer, 2(2):128– 144, 1975. [16] Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, and Alexander Wolff. Multi-sided boundary labeling. Algorithmica, 76(1):225–258, 2016. [17] Christine Lehmann and Jürgen Döllner. Annotating 3d content in interactive, virtual worlds. In Proceedings of the 18th International Conference on 3D Web Technology, pages 67–70. ACM, 2013. [18] Chun-Cheng Lin, Hao-Jen Kao, and Hsu-Chun Yen. Many-to-one boundary labeling. Journal of Graph Algorithms and Applications, 12(3):319–356, 2008. [19] Benjamin Niedermann and Martin Nöllenburg. An algorithmic framework for labeling road maps. In International Conference on Geographic Information Science, pages 308–322. Springer, 2016. [20] Martin Nöllenburg, Valentin Polishchuk, and Mikko Sysikaski. Dynamic one-sided boundary labeling. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 310–319. ACM, 2010. [21] Thierry Stein and Xavier Décoret. Dynamic label placement for improved interactive exploration. In Proceedings of the 6th international symposium on Nonphotorealistic animation and rendering, pages 15–21. ACM, 2008. [22] Markus Tatzgern, Denis Kalkofen, Raphael Grasset, and Dieter Schmalstieg. Hedgehog labeling: View management techniques for external labels in 3d space. In Virtual Reality (VR), 2014 IEEE, pages 27–32. IEEE, 2014. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/71360 | - |
| dc.description.abstract | 傳統地圖演算法注重於對一靜態地圖設計標籤演算法，而動態地圖允許使用者將地圖旋轉、移動，使得傳統地圖演算法無法直接使用在動態地圖上。本論文中考慮了動態軌跡地圖的演算法設計。在給定的軌跡以及點集中，找出不互相重疊的自動標籤化的演算法。在地圖的一邊對地圖上的點集做標籤，找出不重疊且維持相對順序的標籤方法。在論文中我們對軌跡地圖建立起線性規劃模型，並且使用可滑動的標籤方法，使得標籤不須先固定位置，在以往的研究中，標籤是固定在某一個位置。為了提升效率，本論文也提出啟發式演算法來尋找對標籤在地圖右方的標籤方法。最後在論文中比較不同演算法之間的效率。 | zh_TW |
| dc.description.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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-17T05:59:22Z (GMT). No. of bitstreams: 1 ntu-108-R05921034-1.pdf: 4339390 bytes, checksum: 85ad9bd174f969610a3657895fc283dd (MD5) Previous issue date: 2019 | en |
| dc.description.tableofcontents | Contents
論文口試委員審定書i 誌謝ii 摘要iii Abstract iv 1 Introduction 1 2 Preliminaries 4 2.1 Boundary Labeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Trajectory Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 Our ILP-based Method 8 3.1 The Moving Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1.1 Present Interval and Block Interval with Sliding Port . . . . . . . 8 3.1.2 Clustering Points of Moving . . . . . . . . . . . . . . . . . . . . 11 3.1.3 Model of Moving . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.1.4 Algorithm for the Moving Model . . . . . . . . . . . . . . . . . 13 3.2 The Rotating Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2.1 Model of Rotation . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2.2 Algorithm for the Rotation Model . . . . . . . . . . . . . . . . . 19 4 Experimental Results 22 4.1 The Moving Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 The Rotating Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3 Different Label Heights . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5 Conclusion 33 Bibliography 34 | |
| dc.language.iso | en | |
| dc.subject | 動態地圖標籤 | zh_TW |
| dc.subject | 邊界地圖標籤 | zh_TW |
| dc.subject | Boundary Labeling | en |
| dc.subject | Dynamic Map Labeling | en |
| dc.title | 動態軌跡地圖標籤之演算法設計 | zh_TW |
| dc.title | Algorithm Design for Trajectory-based Dynamic Boundary Map Labeling | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 107-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 郭斯彥,雷欽隆 | |
| dc.subject.keyword | 邊界地圖標籤,動態地圖標籤, | zh_TW |
| dc.subject.keyword | Boundary Labeling,Dynamic Map Labeling, | en |
| dc.relation.page | 36 | |
| dc.identifier.doi | 10.6342/NTU201900554 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2019-02-14 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-108-1.pdf 未授權公開取用 | 4.24 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。