Triangulation

平面上散布許多點。只以這些點作為三角形頂點，用線段連接產生三角形，三角形數量越多越好。所有線段形成一個「三角剖分」，通常有許多種。

因為三角形數量越多越好，所以三角剖分的外圍一定是凸包。

三角形的建構順序、建構地點都相當自由，也因此各種凸包演算法都可以順便求得三角剖分。

三角剖分的三角形個數、邊數

計算凸包的三角剖分，再用剩下的點遞迴分割所在的三角形，最後處理共線的點。

令h是凸包點數，令k是其餘點數。凸包的三角剖分得到h-2個三角形；剩下的點，逐次用於三角剖分，每次都多出兩個三角形。由此可知，無論三角剖分長相如何，一個三角剖分固定有(h-2)+2k個三角形，是O(N)。

同理可知，無論三角剖分長相如何，一個三角剖分固定有(2h-3)+3k條邊，亦是O(N)。

這也呼應了平面圖歐拉公式v-e+f=2。

三角剖分的數量

計算不同的三角剖分有多少種，目前除了窮舉法以外沒有更好的演算法，也無人知道這是P問題抑或是NP-complete問題。

Flip Graph

一個三角剖分，翻轉一條邊，可以得到另一個三角剖分。注意到並不是每一條邊都能翻轉的。

二維平面上，給定一個點集合，把所有三角剖分依照翻轉關係連接成一張無向圖，稱作Flip Graph，是連通的。

Flip Graph有著許多謎團，例如點到點最短路徑（兩個三角剖分之間的最少翻轉次數）、直徑、連接性，目前都沒有演算法。

演算法（Graham's Scan）

仿照「Convex Hull: Graham's Scan」，掃除凸包頂點的過程即可進行三角剖分。一如既往，共線的點不好處理。時間複雜度O(NlogN)，主要取決於排序的時間。

演算法（Incremental Method）

仿照「Convex Hull: Incremental Algorithm」，如果當前輸入點在三角形內部，則直接連線至三角形頂點；如果當前輸入點在所有三角形外部，則連線至凸包的切點與凹點。要小心當前輸入點在三角形上的情況。時間複雜度O(N²)。

預先按照XY座標排序所有點（平移的掃描線），就能保證當前輸入點都在所有三角形外部。

當前輸入點與凹點的連線，不超過三角剖分的邊數O(N)。當前輸入點與切點的連線，等同Andrew's Monotone Chain。總時間複雜度O(NlogN)。

演算法（Divide-and-Conquer Method）

仿照「Convex Hull: Divide-and-Conquer Method」，尋找外公切線的過程即可合併左右兩個三角剖分。時間複雜度O(NlogN)。

Minimum Weight Triangulation

線段長度總和最小。NP-hard。是否為NP-complete仍是懸案。

用途是節省印刷墨水。

Maxmin Angle Triangulation

最小的角盡量大。時間複雜度O(NlogN)。

即是「Delaunay Triangulation」。

Minmax Angle Triangulation

最大的角盡量小。時間複雜度O(N²logN)。

《An O(n² log n) time algorithm for the minmax angle triangulation》

Tetrahedralization

「四面體剖分」。三角剖分推廣到三維空間。

四面體剖分的Flip Graph目前完全不知道長什麼樣。

有些形狀不存在四面體剖分，例如Schönhardt Polyhedron：三角柱扭轉凹陷。

Polygon Triangulation

簡單多邊形，沿對角線切割，成為許多三角形。對角線、多邊形互不交錯。通常有許多種。

N個頂點，N-2個三角形，N-3條對角線。

「耳ear」是凸點與兩鄰點組成的三角形，並且不碰其他點、不碰其他邊。「嘴mouth」是凹點與兩鄰點組成的三角形。

耳適合當作剖分對象。但是簡單多邊形一定有耳嗎？

三角形的相鄰關係，恰是一棵樹。超過一點的樹，至少有兩葉。

葉必是耳。超過三點的多邊形，至少有兩耳，且兩耳不重疊。

也就是說，簡單多邊形無論長相，必有耳。甚至可以不斷刵耳，直到剩下三角形，得到三角剖分！

演算法（Incremental Method）

窮舉所有點，判斷是否為耳（的凸點）。若為耳，則刵耳。

多邊形的資料結構是circular linked list，以便快速刵耳。

判斷一個點是否為耳，需時O(N)。未知點最初有N點。刵1次，至多添2點；刵N-3次，至多添2N-6點。未知點至多3N-6點。時間複雜度O(N(3N-6)) = O(N²)。

const int N = 100;					// 頂點數
struct Point {float x, y;} p[N];	// 多邊形
int prev[N], next[N];	// circular linked list
int ear[N];				// -1未知、0非耳、1是耳

bool point_in_triangle(Point p, Point p1, Point p2, Point p3)
{
	Point v1 = p1 - p;
	Point v2 = p2 - p;
	Point v3 = p3 - p;
	float c1 = cross(v1, v2);
	float c2 = cross(v2, v3);
	float c3 = cross(v3, v1);
	return (c1 > 0 && c2 > 0 && c3 > 0)
		|| (c1 < 0 && c2 < 0 && c3 < 0);
}

bool is_ear(int x)
{
	// 耳的凸點
	if (cross(p[x] - p[prev[x]], p[next[x]] - p[x]) <= 0)
		retrun false;
	// 耳內無點
	for (int i = next[next[x]]; i != prev[x]; i = next[i])
		if (point_in_triangle(p[i], p[prev[x]], p[x], p[next[x]]))
			return false;
	return true;
}

void triangulation()
{
	// circular linked list 初始化
	for (int i=0; i<N; ++i)
		prev[i] = i-1, next[i] = i+1;
	prev[0] = N-1, next[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);
			// 找到一耳。
			if (ear[i] == 1) break;
			// 多邊形下一點。
			i = next[i];
		}

cout << "找到耳" << prev[i] << i << next[i];

// 刵耳後，左右鄰點成為未知點。
		ear[prev[i]] = ear[next[i]] = -1;

// 刵耳
		next[prev[i]] = next[i];
		prev[next[i]] = prev[i];
		i = next[i];
	}

cout << "找到耳" << prev[i] << i << next[i];
}

ICPC 4426

演算法（Divide-and-Conquer Method）

一、找到一耳。O(N)。二、刵N-3次。O(N²)。

此法不太健康，參考看看就好。

Art Gallery Problem

一個簡單多邊形，至少要放幾個360度鏡頭，才能看到整個內部、顧及所有地方？

NP-complete問題，難以快速求得答案，但是可以快速估計答案的上限是ceil(n/3)個：三角剖分的點著色數為三，挑一個顏色放滿鏡頭，就能顧及每個三角形。

Minimum Weight Polygon Triangulation

一、所有三角形周長總和最小：Dynamic Programming，時間複雜度O(N²)。此問題與Matrix Chain Multiplication關係密切，時間複雜度可以加速至O(NlogN)。

二、所有對角線長度總和最小：我沒有研究。

UVa 1331

Minmax Angle Polygon Triangulation

最大的角盡量小。我沒有研究。

ICPC 3132 4458

Polygon Partition

Polygon Trapezoidalization

簡單多邊形，每個頂點發射水平線（垂直線），切割成許多梯形、三角形。梯形剖分只有唯一一種。

梯形剖分的用途是建立區域相鄰關係，形成有向無環圖！掃描線的順序就是拓樸順序，方便設計高速演算法。有洞多邊形亦然。

ICPC 2479

Polygon Convex Partition

簡單多邊形，切成許多個凸多邊形。

演算法是Hertel–Mehlhorn Algorithm。我沒有研究。

Acute Triangulation / Non-obtuse Triangulation

簡單多邊形，切成許多個三角形，角度皆小於90°、小於等於90°。

雖然名稱是Triangulation，但是三角形頂點不必是多邊形頂點。名稱取得不好。

《Linear-size Nonobtuse Triangulation of Polygons》