凹多邊形的三角化

Triangulation of Concave Polygons

陳炫璋(Shiuan-Jang Chen)

指導教授 ： 陳漢明

國立臺灣大學/工學院/機械工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.10318

摘要

對簡單多邊形(simple polygon)做三角化(triangulation)在樣式辨認(pattern recognition)、電腦繪圖學(computer graphics)、電腦輔助設計(computer-aided design)以及實體模型建構(solid modeling)等領域中的各種應用是非常有用的，同時它也是計算幾何(computational geometry)最根本的領域之一。一個簡單多邊形可以被分解為數個三角形、數個梯形和數個凸多邊形(convex polygons)，傳統的多邊形切割法則在切割凹多邊形(concave polygons)後沒有將切割出的多邊形獨立分開而發生錯誤。我們將需切割的多邊形變成凸多邊形，三角形必為凸多邊形，所以將多邊形三角形化就可以解決這個問題。

在本論文中提出兩個主要輔助定理(lemmas)，第一個主要輔助定理特別使用在多邊形有數個頂點共線(collinear)時，可以有效減少三角化中對角線(diagonals)使用的數目以及構成三角化三角形的個數；第二個主要輔助定理則是給予對一般簡單凹多邊形三角化明確步驟的準則，其步驟為不斷的從多邊形凹頂點(reflex vertices)為起點連接對角線開始切割三角形，而此切割步驟的時間複雜度達到了線性時間。

關鍵字

三角化演算法 ； 多邊形三角化 ； Two Ears定理 ； 共線頂點 ； 凹頂點 ； 對角線

並列摘要

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.

並列關鍵字

Triangulation Algorithm ； Polygon Triangulation ； Two Ears Theorem ； Collinear Vertices ； Concave Vertex ； Diagonal

參考文獻

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.

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.