陳漢明臺灣大學：機械工程學研究所陳炫璋Chen, Shiuan-JangShiuan-JangChen2007-11-282018-06-282007-11-282018-06-282006http://ntur.lib.ntu.edu.tw//handle/246246/61088對簡單多邊形(simple polygon)做三角化(triangulation)在樣式辨認(pattern recognition)、電腦繪圖學(computer graphics)、電腦輔助設計(computer-aided design)以及實體模型建構(solid modeling)等領域中的各種應用是非常有用的，同時它也是計算幾何(computational geometry)最根本的領域之一。一個簡單多邊形可以被分解為數個三角形、數個梯形和數個凸多邊形(convex polygons)，傳統的多邊形切割法則在切割凹多邊形(concave polygons)後沒有將切割出的多邊形獨立分開而發生錯誤。我們將需切割的多邊形變成凸多邊形，三角形必為凸多邊形，所以將多邊形三角形化就可以解決這個問題。 在本論文中提出兩個主要輔助定理(lemmas)，第一個主要輔助定理特別使用在多邊形有數個頂點共線(collinear)時，可以有效減少三角化中對角線(diagonals)使用的數目以及構成三角化三角形的個數；第二個主要輔助定理則是給予對一般簡單凹多邊形三角化明確步驟的準則，其步驟為不斷的從多邊形凹頂點(reflex vertices)為起點連接對角線開始切割三角形，而此切割步驟的時間複雜度達到了線性時間。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.中文摘要 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一簡單凹多邊形的分解結果 46505731 bytesapplication/pdfen-US三角化演算法多邊形三角化Two Ears定理共線頂點凹頂點對角線Triangulation AlgorithmPolygon TriangulationTwo Ears TheoremCollinear VerticesConcave VertexDiagonalthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/61088/1/ntu-95-R91522618-1.pdf