Publication: Triangulation of Concave Polygons
| dc.contributor | 陳漢明 | en |
| dc.contributor.author | Chen, Shiuan-Jang | en |
| dc.creator | Chen, Shiuan-Jang | en |
| dc.date | 2006 | en |
| dc.date.accessioned | 2007-11-28T07:20:38Z | |
| dc.date.accessioned | 2018-06-28T16:48:04Z | |
| dc.date.available | 2007-11-28T07:20:38Z | |
| dc.date.available | 2018-06-28T16:48:04Z | |
| dc.date.issued | 2006 | |
| dc.description.abstract | In application fields such as pattern recognition, computer graphics, computer-aided design, and solid modeling, the task to triangulate simple polygons is very helpful. The triangulation of simple polygons is one of the most fundamental fields in computational geometry. A simple polygon can be decomposed into triangles, trapezoids, and convex polygons. Traditional clipping polygon algorithms will make mistakes because they cannot separate the clipping polygons independent when clipping concave polygons. We let all the polygons become convex polygons. The problem will be solved by polygon triangulation because triangles are always convex polygons. Two lemmas are proposed in this paper. The first lemma is used for reducing diagonals used and triangles formed in the triangulation especially for the simple concave polygon when several vertices of the polygon are collinear. The second lemma is the basis for a definite triangulation procedure for concave polygons. The procedure is continuously partitioning triangles from reflex vertices. The complexity of the partitioning procedure is in linear time. | en |
| dc.description.tableofcontents | 中文摘要 i 英文摘要 ii 目錄 iii 圖目錄 v 表目錄 vi 第一章 緒論 1 1-1 前言 1 1-2 研究方向 3 1-3 論文組織 4 第二章 文獻回顧 6 2-1 藝術走廊理論 6 2-2梯形法三角化 9 2-3 插入對角線法三角化 10 第三章 簡單凹多邊形三角化與對角線 13 3-1簡單多邊形之定義 13 3-2簡單凹多邊形三角化問題定義 14 3-3對角線(diagonals) 15 3-4簡單多邊形三角化後的對角線數目及三角形數目 21 第四章 含共線頂點之簡單凹多邊形三角化 23 4-1共線頂點線段(Collinear-vertex Segments) 23 4-2只有一個共線頂點線段之多邊形三角化後的對角線數及三角形數 24 4-3數個共線頂點線段之多邊形三角化後的對角線數及三角形數 28 4-4共線頂點多邊形三角化步驟 30 4-5簡單實例 32 第五章 對簡單凹多邊形三角化之演算法 35 5-1凹頂點群(group of reflex vertices) 35 5-2凹頂點群的處理方法 36 5-3以凹頂點為起點加入對角線 37 5-4簡單凹多邊形的三角化 44 第六章 結論 48 參考文獻 39 圖 目 錄 圖2.1多邊形與多邊形之三角化 7 圖2.2利用三種顏色將所有三角形頂點上色示意圖 8 圖2.3 梯形法三角化示意圖 10 圖2.4 耳(ear)的示意圖 12 圖3.1討論簡單凸多邊形的三角化是沒有意義的 15 圖3.2簡單多邊形P的對角線(diagonal)d 16 圖3.3對角線有相交的情形 17 圖3.4利用面積來判斷對角線是否在多邊形內部 18 圖3.5利用輔助線條判斷對角線 20 圖3.6具有六個共線頂點的簡單多邊形 22 圖4.1共線頂點多邊形範例 24 圖4.2只有一個共線頂點線段的多邊形P 26 圖4.3有兩個相交共線頂點線段的多邊形 30 圖4.4以切開的共線頂點線段分割多邊形P的步驟 31 圖4.5共線頂點多邊形三角化範例 34 圖5.1凹頂點群的處理方法種類 37 圖5.2具有5個頂點的簡單凹多邊形 38 圖5.3多邊形P中頂點vj+1 以及 vk-1 皆為凸頂點 39 圖5.4頂點 vj+1 為凹頂點且頂點vj+2 位於區域 R1 40 圖5.5頂點vj+1 為凹頂點且頂點vj+2 位於區域R2 41 圖5.6具有M組凹頂點群的簡單凹多邊形 43 圖5.7具有 M + 1組凹頂點群的簡單凹多邊形 44 圖5.8將凹多邊形分解為數個三角形跟一個凸多邊形的步驟 45 圖5.9一簡單凹多邊形的分解結果 46 | zh_TW |
| dc.format.extent | 505731 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier | zh-TW | en |
| dc.identifier.uri | http://ntur.lib.ntu.edu.tw//handle/246246/61088 | |
| dc.identifier.uri.fulltext | http://ntur.lib.ntu.edu.tw/bitstream/246246/61088/1/ntu-95-R91522618-1.pdf | |
| dc.language | zh-TW | en |
| dc.language.iso | en_US | |
| dc.relation.reference | 1. Alain Fournier, and Delfin Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics, Vol.3, No.2, 1984, pp.153-174. 2. Bernard Chazelle, and Janet Incerpi, Triangulation and Shape-complexity, ACM Transactions on Graphics, Vol.3, No.2, 1984, pp.135-152. 3. Bernard Chazelle, Triangulating A Simple Polygon in Linear Time, Discrete Computer Geometry, Vol.6, No.4, 1991, pp.485-524. 4. Gary Hosler Meisters, Polygons Have Ears, The American Mathematical Monthly, Vol.82, No.6, 1975, pp.648-651. 5. Godfried Toussaint, Efficient Triangulation of Simple Polygons, The Visual Computer, Vol.7, No.5&6, 1991, pp.280-295. 6. H. Fuchs, and B. F. Naylor, “On Visible Surface Generation by A Priori Tree Structures,” ACM SIGGRAPH 80, July 1980, pp.124-133. 7. Han Ming Chen, and Wen Teng Wang, “The Feudal Priority Algorithm on Hidden-Surface Removal,” ACM SIGGRAPH 96, August 1996, New Orlands, USA. 8. Hossam ElGindy, Hazel Everett, and Godfried Toussaint, Slicing an Ear in Linear Time, Pattern Recognition Letters, Vol.14, No.7, 1993, pp.719-722. 9. Jean-Daniel Boissonnat, and Mariette Yvinec, Algorithmic Geometry, Cambridge University Press, United Kingdom, 1998. 10. Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud, and Mariette Yvinec, Triangulations in CGAL, Proceedings of the sixteenth annual symposium on Computational Geometry, Hong Kong, 2000, pp.11-18. 11. Joseph O’Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1986. 12. Joseph O'Rourke, Computational Geometry in C, Cambridge University Press, United Kingdom, 1993. 13. Kenneth L. Clarkson, Robert E. Tarjan, and Christopher J. van Wyk, A Fast Las Vegas Algorithm for Triangulation a Simple Polygon, Discrete Computer Geometry, Vol.4, No.3, 1989, pp.423-432. 14. M.R. Garey, D.S. Johnson, F.P. Preparata, and R.E. Tarjan, Triangulating a simple polygon, Information Processing Letters, Vol.7, No.4, 1978, pp.175-180. 15. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, Berlin, 1997. 16. Marko Lamot, and Bozut Zalik, Algorithms for triangulating simple polygons, Proceedings of 22nd International Conference on Information Technology Interfaces, Pula, Croatia, June 2000, pp.429-436. 17. Martin Held, Efficient and reliable triangulation of polygons, Proceedings of the Computer Graphics International 1998, June, Hannover, Germany, 1998, pp.633-643. 18. Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos, Linear-Time Triangulation of a Simple Polygon Made Easier Via Randomization, Proceedings of the sixteenth annual symposium on Computational Geometry, Hong Kong, 2000, pp.201-212. 19. Raimund Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry: Theory and Applications, Vol.1, No.1, 1991, pp.51-64. 20. Remi P. Ronfard, and Jarek R. Rossignac, Triangulating multiply-connected polygons: A simple, yet efficient algorithm, EuroGraphics, Vol.13, No.3, 1994, pp.281-292. 21. Stefan Hertel, and Kurt Mehlhorn, Fast Triangulation of Simple Polygons, Proceedings of 4th International Conference on Fundamental Computer Theory, Lecture Notes in Computer Science, Vol.158, Springer-Verlag, 1983, pp.207-218. 22. Xianshu Kong, Hazel Everett, and Godfried Toussaint, The Graham Scan Triangulates Simple Polygons, Pattern Recognition Letters, Vol.11, No.7, 1991, pp.713-716. 23. 劉致宏(Liu, Jyh-Hong), 物件排序法則及應用, 國立臺灣大學機械工程學研究所, 碩士論文, 中華民國86年6月. | zh_TW |
| dc.subject | 三角化演算法 | en |
| dc.subject | 多邊形三角化 | en |
| dc.subject | Two Ears定理 | en |
| dc.subject | 共線頂點 | en |
| dc.subject | 凹頂點 | en |
| dc.subject | 對角線 | en |
| dc.subject | Triangulation Algorithm | en |
| dc.subject | Polygon Triangulation | en |
| dc.subject | Two Ears Theorem | en |
| dc.subject | Collinear Vertices | en |
| dc.subject | Concave Vertex | en |
| dc.subject | Diagonal | en |
| dc.title | Triangulation of Concave Polygons | en |
| dc.type | thesis | en |
| dspace.entity.type | Publication |
Files
Original bundle
1 - 1 of 1