Triangulation

一個多邊形，沿對角線分割成三角形，對角線不交叉，稱做「三角剖分」。

實心多邊形，有N個頂點，恰可剖分成N-2個三角形（用掉N-3條對角線、內角總和(N-2)π）。證明很簡單，宛如刀削麵，不斷從邊邊角角割下三角形，同時觀察多邊形頂點數量，即可證得。

空心多邊形，只要知道內與外各有多少頂點，就能推算三角形數量。留給讀者吧。

總之，一個多邊形的三角形數量是固定的。至於如何剖分，則是接下來的課題。

Ear / Mouth

「耳」是凸點與鄰點組成的三角形，而且對角線不與其他邊相交。「嘴」是凹點與鄰點組成的三角形。剩下來的點並沒有被叫做鼻子。

一個三角剖分，把三角形的相鄰關係，建立為圖，恰好是一棵樹。即是平面對偶。

耳就是樹葉。由此可得「兩耳定理」：四個點以上的多邊形至少有兩耳，且兩耳不重疊。

也就是說，無論是哪種多邊形，必可不斷刵之！

演算法：判斷一點是否為耳（判斷兩鄰點是否能連成對角線）

這很簡單，窮舉多邊形所有點，看看是否都在耳外，便是耳。可用外積判斷內外。O(N)。

也可以窮舉多邊形所有邊，看看是否與對角線皆不相交，便是耳。線段相交實作麻煩，故乏人問津。O(N)。

演算法：找到一耳

O(N)，原理是Divide and Conquer，不太健康，鮮為人知。

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html

演算法：實心多邊形的三角剖分

用O(N)時間找個耳，持續刵N-3個耳即得。O(N^2)。

比較健康的方式是，逐點判斷是否為耳，勤做紀錄，亦可達到O(N^2)。資料結構是doubly linked list。

int ear[9]; // 0非耳、1是耳、-1未知也 int L[9], R[9]; // doubly linked list void triangulation(vector<Point>& polygon) { int N = polygon.size(); // 初始化 doubly linked list for (int i=0; i<N; ++i) L[i] = i-1, R[i] = i+1; L[0] = N-1, R[N-1] = 0; // 一開始所有點都不知是否為耳 memset(ear, -1, sizeof(ear)); // 刵N-3次 int i = 0; for (int k=0; k<N-3; ++k) { // 嘗試找到一耳，根據兩耳定理一定找得到。 while (true) { // 未知，則算。 if (ear[i] == -1) ear[i] = is_ear(i, polygon); // 找到一耳。 if (ear[i] == 1) break; // doubly linked list的下一點。 i = R[i]; } cout << "找到一耳" << L[i] << i << R[i]; // 刵。僅有左右鄰點受到影響，狀態成為未知。 ear[R[i]] = ear[L[i]] = -1; // 從doubly linked list去除此點。 R[L[i]] = R[i]; L[R[i]] = L[i]; i = R[i]; } cout << "找到一耳" << L[i] << i << R[i]; }

用均攤分析求時間複雜度：

不知是否為耳的點，一開始有N點，之後每刵一次最多增加2點，共刵N-3次──不知是否為耳的點，最多出現3N-6點。

判斷是否為耳，需時O(N)，最多判斷3N-6次，推得總時間複雜度是O(N^2)。

ICPC 4426

Trapezoidalization

一個多邊形，沿著穿過頂點的水平線分割成梯形，稱做「梯形剖分」。

ICPC 2479 3702

Triangulation

UVa 12310

Hertel-Mehlhorn algorithm

O(N^2 * logN)。

Edelsbrunner et al. An O(n2 log n) time algorithm for the minmax angle triangulation.

ICPC 3132 4458

凸多邊形的三角剖分

到處皆可刵，刵完仍是凸多邊形，仍是到處皆可刵，時間複雜度為O(N)。感覺像是連續平滑函數作微分，不管怎麼微都還是可微。

要得到三角形周長總和最小的三角剖分，採用Dynamic Programming時間複雜度為O(N^3)，得降至O(N^2)；採用Greedy Method時間複雜度為O(NlogN)。此問題與Matrix Chain Multiplication問題有密切關係。

簡單多邊形：邊不相交的多邊形
問題：一個簡單多邊形，至少要放幾個360度鏡頭，才能看到所有地方？
NPC問題
上限是ceil(n/3)，證明是：簡單多邊形三角化後，點著色數為三，在同一個顏色放鏡頭。

UVa 10762 ICPC 3306