(3.237.178.91) 您好!臺灣時間:2021/03/07 13:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張志強
研究生(外文):Zhong Zhi-Chong
論文名稱:多邊形的最佳三角形化
論文名稱(外文):The Optimal Polygon Triangulation
指導教授:陳漢明陳漢明引用關係
指導教授(外文):Cheng Han-Ming
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:機械工程學研究所
學門:工程學門
學類:機械工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:中文
論文頁數:68
中文關鍵詞:三角形化電腦繪圖學
外文關鍵詞:triangulationcomputer graphics
相關次數:
  • 被引用被引用:0
  • 點閱點閱:228
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載: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. )

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔