# 臺灣博碩士論文加值系統

(34.239.167.149) 您好！臺灣時間：2022/06/29 17:02

:::

### 詳目顯示

:

• 被引用:0
• 點閱:264
• 評分:
• 下載:0
• 書目收藏:0
 中文摘要 在電腦繪圖學中，多邊形的切割幾乎是無法避免的事，傳統的多邊形切割法則在切割凹多邊形後沒有將切割出的多邊形獨立分開而發生錯誤，而對於此種情形的解決的方法有兩種，一為改進傳統的多邊形切割法則;另一為將需切割的多邊形變成凸多邊形，三角形必為凸多邊形，所以將多邊形三角形化就可以解決這個問題。 本論文將先介紹幾個多邊形三角形化的法則，針對要使用的多邊形基本性質做說明，並對在多邊形三角形化過程中會遇到的問題提出解決方法，然後介紹我們發展的簡單多邊形三角形化法則，它保証三角形化的三角形數為最少。 最後，我們探討非簡單多邊形的三角形化，並將選取三種形態的非簡單多邊形為例子，將之變成多個簡單多邊形的組合，再利用前面的簡單多邊形三角形化的法則，將之三角形化。
 The Optimal Polygon Triangulation Zhi-Chong Zhong Abstract It is almost impossible to avoid clipping polygon in computer graphics. Traditional clipping polygon algorithms will make mistakes because they cannot separate the clipping polygons independent when clipping concave polygons. There are two methods to solve the problem: one is to improve the traditional clipping polygons, the other is to let all the polygons become convex polygons. The problem will be solved by polygon triangulation because triangles are always convex polygons. In this research we are going to introduce several polygon triangulation algorithms, then we will explain the basic habitudes of the polygons that we will use in the latter, and then we will propose the methods to solve the problems we will meet during polygon triangulation. At last, we will introduce the simple polygon triangulation algorithm that guarantees the least number of the triangles after polygon triangulation. At least, we will discuss the triangulation of the nonsimple polygon. We select three types of the nonsimple polygons as the examples. We let they become the collections of the simples polygons. Then we can use the previous simple polygon triangulation algorithm to make the polygon triangulation.
 目錄 第一章 緒論................................................1 1.1 研究背景..............................................1 1.2 研究方向...............................................2 1.3 論文組織..............................................3 第二章 文獻回顧...........................................5 2.1 藝術走廊理論..........................................5 2.2 利用多邊形的單調性來三角化多邊形.......................9 2.2.1單調性………………………………………………………………9 2.2.2三角化的步驟…………….………………………………………10 2.2.2.1先將多邊形單調化……………………………………………11 2.2.2.2三角化方式1-分成兩組點串列………………………………11 2.2.2.3三角化方式2-水平切割或垂直切割…………………………13 第三章 簡單多邊形三角化的存在性.........................15 3.1 簡單多邊形之定義....................................15 3.2 簡單多邊形三角化之存在性............................16 3.2.1 對角線的存在性………………………………………………。16 3.2.2 簡單多邊形三角化後的三角形數目....................21 第四章 簡單多邊形三角形化法則…………………………………28 4.1 問題的描述........................................…28 4.1.1 發展三角化法則的想法..............................28 4.1.2 簡單多邊形的分類...................................29 4.1.3 非簡單多邊形…………………………………………………29 4.2對角線的性質..........................................29 4.2.1 與多邊形的邊發生相交………………………………30 4.2.2內外性…………………………………………………31 4.3共線頂點多邊形……………………………………………36 4.3.1 共線頂點多邊形的定義…………………………………36 4.3.2共線點多形邊三角形化方法……………………………38 4.3.3實例………………………………………………………38 4.4 凹多邊形的處理方式……………………………………….38 4.4.1 凹角的性質………………………………………………39 4.4.2 凹角的處理方式…………………………………………41 4.4.3 凹角處理實例……………………………………………43 4.5 簡單多邊形三角化法則………………………………………45 4.5.1 三角化法則………………………………………………..45 4.5.2 多邊形三角化的實例……………………………………..46 第五章 非簡單多邊形之切割............................49 5.1 非簡單多邊形.....................................49 5.2 非簡單多邊形的三角化..............................51 5.2.1多邊形頂點的排序…………………………………………52 5.2.2將非簡單多邊形變成簡單多邊形的組合………………….53 5.2.2.1四個以上的邊共頂點的非簡單多邊形…………………53 5.2.2.2邊相交的非簡單多邊形…………………………………55 5.2.2.3 有內孔之多邊形………………………………………57 5.3 總結...........................................59 第六章 結論與未來展望...............................62 6.1 結論.............................................62 6.2 未來展望.........................................63 參考文獻..............................................57
 參考文獻[Berg97]Mark de Berg, Marc vans Kreveld and Mark Overbears. Computational Geometry Algorithms and Applications, Springer-Verlag, Berlin Heidelberg, 1997. (Chapter 3: Polygon Triangulation.)[Bois98]Jean-Daniel Boissonnat, Algorithmic Geometry, Cambridge University Press, 1998 (Chapter 12 : Triangulation in Dimension 2)[Chaz84]Bernard Chazelle and Janet Incerpi, “Triangulation and Shape-complexity,” ACM Transition on Graph,Vol. 3(2), 1984, pp.135-152.[Clar89]Kenneth L. Clarkson, Robert E. Tarjan, and Christopher J.Van Wyk. “A Fast Las Vegas Algorithm for Triangulating a Simple polygon”. Discrete Computer Geometry, Vol. 4, 1989, pp.423-432.[Chaz91]Bernard Chazelle, Department of Computer Science, Prinception University, “Triangulating A Simple Polygon in Linear Time,” Discrete Computer Geometry, Vol.6, 1991pp.485-524.[Catm74]E. Catmull, A subdivision Algorithm for Computer Display of Curved Surfaces, Ph.D. Dissertation, University of Utah, Salt Lake City, Utah, 1974.[Chen96]Han Ming Chen, and Wen Teng Wang, “The Feudal Priority Algorithm on Hidden-Surface Removal,” ACM SIGGRAPH 96, August 1996, New Orlands, USA.[Four84]Alain Fournier and Delfin Y. Montuno, “Triangulating Simple Polygons and Equivalent Problems”. ACM Transition on Graph, Vol. 3(2), 1984, pp.153-174.[Fuch80]H. Fuchs, , and B. F. Naylor, “On Visible Surface Generation by A Priori Tree Structures,” ACM SIGGRAPH 80, July 1980, pp.124-133.[Liu 97]劉致宏(Liu, Jyh-Hong), 物件排序法則及應用, 國立臺灣大學機械工程學研究所, 碩士論文, 中華民國86年6月.[Lee86]D. T. Lee and A. K. Lin, “Generalized Delaunay Triangulation for Planar Graphs,” Discrete Computer Geometry, Vol. 1, 1986, pp.201-217.[O’Rou94]Joseph O’Rourke, Computational Geometry In C, Cambridge University Press, 1994. (Chapter 1: Polygon Triangulation.)[O’Rou87]Joseph O’Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1986. (Chapter 1: Polygon Partitions, Chapter 5: General Polygon With Hole. )
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 物件排序法則及應用

 無相關期刊

 1 以真空結冰達到污水之純化 2 風道中圓管對線流扇流場之噪音與性能之影響 3 滑片型迴轉式壓縮機結構尺寸與效率之最佳化設計 4 電腦輔助拆卸程序產生及評估 5 半導體產業潔淨室之矽甲烷燃燒控制技術 6 煙道彎管內偏流現象之研究 7 模組化晶圓生產系統分析評估與規劃 8 針對完全自由市場石化暨燃油整體生產規劃 9 精密磨床熱誤差模擬分析 10 多邊形描述及其應用 11 電動機車馬達驅動控制器之研製 12 直接驅動車輪馬達最佳驅動波形之研究 13 雙圓管下落液膜蒸發/吸收之熱質傳研究 14 異向性材料層域與壓延問題的理論解析 15 以分散式元件為基礎所發展之製造系統架構

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室