前言

這篇文章原本是我在學習計算幾何學(非ICPC相關(guān))過程中的一篇筆記俱两。由于學校某課程的原因，經(jīng)過重新整理后寫出來曹步。    

在學習的過程中宪彩，參考了許多資料，包括清華大學鄧老師的計算幾何書籍讲婚，視頻尿孔，知乎上的一些文章和各種論文，并且偷了不少圖。  
  
由于在查找資料的過程中活合，并沒有找到一篇較為完整且較為清晰的中文資料雏婶，于是決定把這篇文章發(fā)出來。   

但由于本人水平極為有限芜辕，許多地方可能是錯的，僅僅代表我自己的理解块差。

本來計劃發(fā)知乎上侵续，結(jié)果因為知乎對markdown支持太辣雞了所以擱置，現(xiàn)在又重新翻了出來憨闰。

多邊形三角剖分 (Triangulation)

三角剖分有兩種状蜗，一種是對多邊形的三角剖分，一種是對平面點集的三角剖分鹉动。這里討論的是對多邊形的三角剖分轧坎。

美術(shù)館問題 (Art Gallery Problem)

如何用最少的守衛(wèi)看守美術(shù)館, 并使得美術(shù)館的每個角落都在守衛(wèi)的視野之中？
一個等價的問題是：需要多少盞燈來完全照亮整個房間泽示。

美術(shù)館問題

樸素的上下界

將美術(shù)館抽象成一個多邊形缸血，那么當這個多邊形存在核時，顯然只需要一個守衛(wèi)就能完成械筛。
考慮最壞情況捎泻，在多邊形任意頂點上都放置一個守衛(wèi)，也一定可以完成埋哟。
所以守衛(wèi)的數(shù)量在 到 之間笆豁。

很遺憾，對于一般多邊形赤赊，求解最少需要多少守衛(wèi)能夠完成任務(wù)的問題是 的闯狱。

Chvátal 美術(shù)館定理 (Chvátal Art Gallery Theorem)

將美術(shù)館抽象為多邊形，守衛(wèi)抽象為點抛计。
對于任意邊數(shù)為 的多邊形哄孤，最多只需要 個點就一定能完全覆蓋了。而且存在多邊形確實需要 個點才能覆蓋吹截。

最壞情況

如何證明沒有更壞的情況双饥？

Fisk 的簡短證明

顯然對于一個三角形只需要在其一個頂點上放置一個點就可以覆蓋這個三角形。
引入若干條不相交的對角線(diagonal)對多邊形進行三角剖分弟断。對角線的定義為：連接多邊形一對頂點的線段咏花。
可以證明：任何一個頂點數(shù)量為 的簡單多邊形都存在一個三角剖分，使其分解為 個三角形。
證明可以使用數(shù)學歸納法的思想昏翰。任取多邊形的一條對角線苍匆，將多邊形切分為頂點數(shù)量分別為 ， 的多邊形棚菊，有 且 浸踩，又根據(jù)假設(shè)： 個頂點的簡單多邊形能分解為 個三角形。所以包含的三角形數(shù)量為 個统求。

將多邊形三角剖分后检碗，形成了一張圖 ，點集為多邊形的頂點码邻，邊集為多邊形的邊和對角線的并集折剃。觀察 的對偶圖，容易看出是一棵樹像屋。所以對于 一定能夠進行三染色怕犁。
對于相鄰的兩個三角形，不重合的兩個點染色必定相同己莺，而且每個三角形的三個頂點必須一一對應這三種顏色奏甫。所以從任意三角形開始反復迭代即可完成對整張圖的三染色。

頂點的三染色

在這三種顏色中凌受，任選一種顏色就可以完成覆蓋扶檐。根據(jù)鴿巢原理，最多選擇 個點就足夠了胁艰。

以上是美術(shù)館問題的一個近似解款筑，指出對于任意 個點的簡單多邊形，雖然求解最少使用多少點進行全覆蓋是 的腾么，但是可以證明可以使用不超過 個點進行全覆蓋奈梳。
在證明的過程中使用了三角剖分這一經(jīng)典的幾何算法，但是對于三角剖分的一些細節(jié)還沒有考慮解虱。比如：是否任意簡單多邊形都能進行三角剖分攘须？如果簡單多邊形帶洞，是否依然能三角剖分殴泰？

三角剖分

首先界定研究對象于宙，這里的三角剖分指的是對簡單的，可以帶空洞的多邊形的三角剖分悍汛。
簡單多邊形是邊不相交的多邊形捞魁，根據(jù) 曲線定理，這樣的多邊形將平面分為一個外部區(qū)域和內(nèi)部區(qū)域离咐。

規(guī)定：對于不帶洞的簡單多邊形谱俭，沿著邊逆時針走一圈為正方向奉件。對于帶洞的簡單多邊形，沿著外邊界逆時針走一圈為正方向昆著，沿著內(nèi)部的洞順時針走一圈為正方向县貌。
這樣能夠保證任何時刻沿著邊界前進時，內(nèi)部區(qū)域都在左手側(cè)凑懂。

雙耳定理 (Two Ears theorem)

耳：對于多邊形中相鄰的三個頂點 煤痕，如果向量 且 不包含任意其他頂點，則 三點構(gòu)成一個耳接谨。直觀的看就是三個點滿足局部凸性而且內(nèi)部是空的摆碉。
對于一個多邊形，可以割去一個耳疤坝，會在不改變其他性質(zhì)的情況下兆解，使得多邊形的頂點數(shù)減小馆铁。

耳

雙耳定理指出對于任意簡單多邊形跑揉，至少有兩個耳。
證明使用了數(shù)學歸納法埠巨，這里略历谍。實際上證明的思路和下面的三角剖分構(gòu)造的思路是一樣的。

三角剖分存在性的證明

使用數(shù)學歸納法辣垒。
對于一個多邊形望侈，有兩種屬性，頂點數(shù) 和空洞數(shù) 勋桶。

基礎(chǔ)情況： 時脱衙，多邊形本身就是三角形，顯然存在三角剖分例驹。
假設(shè)：對于一個頂點數(shù)為 捐韩， 空洞數(shù)為 的多邊形。任意滿足： 或 的多邊形都存在三角剖分鹃锈。
實際上這是一個全序關(guān)系荤胁，對于任意兩個多邊形，能夠基于這個關(guān)系進行比較屎债。

考慮多邊形 最下面的一個頂點 （如果有多個最下面的點仅政，取最左邊的一個點），有兩種情況盆驹。

1. 如果 是一個耳圆丹，那么直接切去，化為頂點數(shù)為 的多邊形躯喇。

2. 如果 不是耳运褪，那么找到多邊形其他點中距離 最近的一個點 ，連接 進行切開，又有兩種情況：

   構(gòu)造性證明
   1. 如上圖左所示秸讹， 在外邊界上檀咙，那么多邊形將化為兩個規(guī)模更小的多邊形。
   2. 如上圖右所示璃诀， 在空洞上弧可，新的多邊形雖然頂點數(shù)量增加了，但是空洞的數(shù)量減少了劣欢∽厮校基于上面的全序關(guān)系，新多邊形和原來相比規(guī)模更小凿将。

根據(jù)歸納假設(shè)校套，規(guī)模更小的多邊形存在三角剖分，那么多邊形 也存在三角剖分牧抵。證明結(jié)束笛匙。

一些其他性質(zhì)

唯一性：

不唯一，最簡單的凸四邊形就有兩種三角剖分犀变。

三角剖分種數(shù)的最值：

最小值為 妹孙，最簡單的凹四邊形只有一種剖分方式，以此可以構(gòu)造出其他情況获枝。
最大值在凸多邊形的時候達到蠢正。
假設(shè)多邊形頂點數(shù)為 ，那么遞推式為：

即對應第 項的 數(shù)。

時間復雜度

多邊形的三角剖分可以在 時間復雜度內(nèi)完成，下面是三角剖分算法例朱，分為兩個步驟：單調(diào)多邊形分解和單調(diào)多邊形內(nèi)三角剖分。

單調(diào)多邊形分解 (Monotone Decomposition)

多邊形單調(diào)性

如果一條鏈上每條線段對于一條直線 的投影只在折點處相交雹舀，那么折線對直線 具有單調(diào)性。

單調(diào)折線

如果一個多邊形能被分成互補的兩條鏈谎脯，而且這兩條鏈都對直線 單調(diào)葱跋，那么這個多邊形對 單調(diào)。

單調(diào)多邊形

為了方便源梭，在下面的算法中娱俺，單調(diào)多邊形指的是對 軸單調(diào)的多邊形，正如上圖所示废麻，是一個對 軸單調(diào)的多邊形荠卷。

對于一個單調(diào)多邊形，可以快速而簡單地進行三角剖分烛愧。但是首先必須要把整個的簡單多邊形分解成若干個單調(diào)多邊形油宜。
算法如下掂碱。

頂點類型定義

對于多邊形上的每一個點，可以分成 類：開始點 (start vertex)慎冤，結(jié)束點(end vertex)疼燥，分裂點 (split vertex)，合并點 (merge vertex)和普通點 (regular vertex)蚁堤。
假設(shè)當前點為醉者，其前驅(qū)為，后繼為披诗。并且為了方便撬即，我們假設(shè)任意兩個點之間的縱坐標不同，雖然對于縱坐標相同的情況呈队，這個算法依然正確剥槐。

1. 開始點：當且僅當 和 都在 下方，并且內(nèi)角 宪摧。
2. 結(jié)束點：當且僅當 和 都在 上方粒竖，并且內(nèi)角 。
3. 分裂點：當且僅當 和 都在 下方绍刮，并且內(nèi)角 温圆。
4. 合并點：當且僅當 和 都在 下方挨摸，并且內(nèi)角 孩革。
5. 普通點：不滿足前 種的全都是普通點。

分裂點和合并點是破壞多邊形單調(diào)性的原因得运，所以需要在這兩個點的地方引進一條內(nèi)對角線膝蜈，將多邊形拆分成兩個小的多邊形，以此來保證兩個小多邊形是單調(diào)的熔掺。顯然對于分裂點饱搏，我們需要向上引入一條內(nèi)對角線，對于合并點置逻，需要向下引入一條內(nèi)對角線推沸。

以分裂點為例，如上圖所示券坞，在分裂點 處鬓催，我們需要找到在左右邊境內(nèi)上方最近的第一個點，圖中為 恨锚，然后引入一條內(nèi)對角線宇驾，與此同時，原本的大多邊形也會分裂成兩個小多邊形猴伶。

需要注意的是左右邊界课舍，并不是上方最近的第一個點就是我們要找的 塌西，因為這個點可能出現(xiàn)在其他小多邊形中。所以我們需要維護多個小多邊形的邊界筝尾，并且能夠查找和修改捡需。

對于合并點，處理方法也是大同小異的筹淫。于是我們的算法就呼之欲出了栖忠。

掃描線 (sweep line)算法

設(shè)置一條水平掃描線，從上向下依次掃過每個頂點贸街。對于每個點庵寞，按照其類型進行操作。對于開始點薛匪，結(jié)束點和普通點捐川，維護小多邊形的邊界信息。對于分裂點逸尖，連接內(nèi)對角線并且分裂多邊形古沥。
合并點也是同樣如此，只不過是從下往上重新做一次娇跟。

需要的數(shù)據(jù)結(jié)構(gòu)：由于我們需要查找和維護每個小多邊形當前的邊界岩齿，所以使用二分搜索樹。

具體來說：對于第一次從上往下的掃描到的每個點苞俘，我們要做的是：

1. 開始點：說明一個新的小多邊形開始了盹沈，將其左右邊界加入樹。
2. 結(jié)束點：說明一個小多邊形結(jié)束了吃谣，找到結(jié)束點左右邊界乞封，從樹中刪除。
3. 分裂點：從樹中找到這個點所在多邊形的左右邊界和點上方最近的一個點岗憋，連接內(nèi)對角線肃晚，加入兩個新多邊形的信息，刪除舊的大多邊形仔戈。
4. 合并點：在這一次我們不連對角線(第二次從下到上的掃描才連)关串，僅僅需要合并兩個小多邊形的邊界信息成大多邊形，并且加入樹监徘。
5. 普通點：維護當前多邊形的邊界信息晋修。

該算法較為復雜，信息量較多耐量，可以結(jié)合下圖掃描的過程手動模擬幫助理解飞蚓。

掃描過程

代碼

//寫是寫了，但是還沒測過廊蜒，手出了幾組小數(shù)據(jù)好像沒什么問題趴拧。
//由于偷懶用了std::set溅漾，某個地方好像復雜度有點問題，看心情修吧著榴，先咕了添履。

時間復雜度

排序 ，掃描的過程中對每個點都需要查找和維護二叉平衡樹脑又，每次耗費 暮胧， 一共 個點。所以總復雜度 问麸。

三角剖分單調(diào)多邊形 (Triangulating Monotone Polygons)

由于單調(diào)多邊形具有良好的性質(zhì)往衷，我們可以從貪心的想法出發(fā)，沿著多邊形的左右邊界逐步向下掃描严卖，遇到一個頂點時進行操作席舍。

單調(diào)棧

可以考慮什么情況下，當掃描到一個點時能剖分出一個三角形哮笆，什么時候不能来颤。舉個例子：

情況1

情況2

情況3

如果學過 掃描法求凸包的話衡创，一定會發(fā)現(xiàn)非常相似。于是我們使用一個單調(diào)棧保存前面的點的信息晶通，單調(diào)棧內(nèi)的元素滿足：

1. 高度遞增：因為我們從上往下掃描璃氢，所以棧頂元素一定是最低的。
2. 在同一側(cè)：如果有異側(cè)元素出現(xiàn)狮辽，那么可以不停地向上剖分一也，直到剩下的都是同側(cè)為止巢寡。
3. 棧內(nèi)連續(xù)的三個元素之間的內(nèi)角 （單調(diào)性）。

掃描線算法

與上一個掃描線算法類似椰苟，從上到下設(shè)置一條水平掃描線抑月，一開始先將最高的點加入棧，然后開始向下掃描舆蝴，每個點按照上面的分類進行操作谦絮。

由于這個算法較為簡單，這里不詳細描述每個步驟洁仗，只給出代碼层皱。

代碼

以下代碼僅供參考和幫助理解算法用，實際上許多 如三點共線赠潦，或者是兩個點縱坐標相同奶甘，都沒考慮，所以幾乎不存在魯棒性祭椰。這個代碼僅僅能夠在給定單調(diào)多邊形非常正常的情況下給出正確的對角線臭家。

輸入： 個點，逆時針給出的多邊形坐標： 方淤。
輸出：若干條對角線連接的兩個點的編號 钉赁，表示點 和 相連。

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db eps = 1e-6;
int sign(db k)
{
    if (k > eps)
        return 1;
    else if (k < -eps)
        return -1;
    return 0;
}
int cmp(db k1, db k2) { return sign(k1 - k2); }
struct point
{
    db x, y;
    point operator+(const point &k1) const { return (point){k1.x + x, k1.y + y}; }
    point operator-(const point &k1) const { return (point){x - k1.x, y - k1.y}; }
    point operator*(db k1) const { return (point){x * k1, y * k1}; }
    point operator/(db k1) const { return (point){x / k1, y / k1}; }
    int operator==(const point &k1) const { return cmp(x, k1.x) == 0 && cmp(y, k1.y) == 0; }
    bool operator<(const point k1) const
    {
        int a = cmp(y, k1.y);
        if (a == -1)
            return 0;
        else if (a == 1)
            return 1;
        else
            return cmp(x, k1.x) == 1;
    }
};
db cross(point k1, point k2) { return k1.x * k2.y - k1.y * k2.x; }
db dot(point k1, point k2) { return k1.x * k2.x + k1.y * k2.y; }

//--------------------------------------------------------

const int maxn = 1e5 + 10;

int side[maxn];

vector<pair<int, int>> TriangulateMonotonePolygon(vector<pair<point, int>> v)
{
    if (v.size() <= 3)
        return {};
    vector<pair<int, int>> ans;
    int n = v.size();
    auto vv = v;
    sort(vv.begin(), vv.end());
    for (int i = (vv[0].second + 1) % n; i < vv[n - 1].second; i = (i + 1) % n)
        side[i] = 0; //* left: 0  right: 1
    for (int i = (vv[n - 1].second + 1) % n; i < vv[0].second; i = (i + 1) % n)
        side[i] = 1;

    sort(v.begin(), v.end());

    stack<pair<point, int>> st;
    st.push(v[0]);
    st.push(v[1]);
    for (int i = 2, sd = side[v[i].second]; i < n - 1; i++)
    {
        if (side[v[i].second] == side[st.top().second]) //same side
        {
            if (st.size() < 2)
            {
                st.push(v[i]);
                continue;
            }
            while (st.size() >= 2)
            {
                auto top = st.top();
                st.pop();
                auto top2 = st.top();

                if (sd == 0 && sign(cross(top.first - top2.first, v[i].first - top.first)) == -1 ||
                    (sd == 1 && sign(cross(top.first - top2.first, v[i].first - top.first)) == 1))
                {
                    st.push(top);
                    break;
                }
                ans.emplace_back(v[i].second, top2.second);
            }
            st.push(v[i]);
        }
        else
        {
            auto top = st.top();
            while (st.size() > 1)
            {
                ans.emplace_back(v[i].second, st.top().second);
                st.pop();
            }
            st.pop();
            st.push(top);
            st.push(v[i]);
        }
    }
    int cnt = st.size(), now = st.size();
    while (!st.empty())
    {
        if (now == cnt || now == 1)
        {
            st.pop();
            continue;
        }
        ans.emplace_back(v[n - 1].second, st.top().second);
        st.pop();
    }
    return ans;
}

vector<pair<point, int>> input;

int main()
{
    int n;
    cin >> n;
    input.resize(n);
    for (int i = 0; i < n; i++)
        cin >> input[i].first.x >> input[i].first.y, input[i].second = i;
    auto ans = TriangulateMonotonePolygon(input);
    cout << "diagonal id:" << endl;
    for (auto x : ans)
        cout << x.first << " " << x.second << endl;
}

時間復雜度

排序 携茂。單調(diào)棧由于每個點只會入棧出棧一次你踩，均攤 ，有 個點讳苦，所以 带膜。 總復雜度 。
實際上鸳谜，如果給定的單調(diào)多邊形已經(jīng)排好序膝藕，并且標好左右邊界的標記，可以把排序的復雜度去掉咐扭，這一部分的總復雜度就變?yōu)?芭挽。而這一步可以在單調(diào)多邊形分解時做到。

其他

正交多邊形 (Orthogonal Polygon) 覆蓋

正交多邊形指的是所有邊都互相垂直或平行的多邊形蝗肪。
與三角剖分類似袜爪，由于正交多邊形自身良好的性質(zhì)，可以做到 個點就可以完全覆蓋薛闪，采用的是凸四邊形剖分辛馆。

凸四邊形剖分

四面體剖分 (Tetrahedralization)

當情況推廣為高維，對于一個空間中的多面體豁延，是否能夠進行四面體剖分呢昙篙？
答案是否倔韭。實際上不僅做不到四面體剖分，甚至不能保證覆蓋瓢对。

前面有提到寿酌，在二維多邊形中，如果每個頂點都放置一個守衛(wèi)硕蛹，那么多邊形的所有地方否會被覆蓋到醇疼，然后以此繼續(xù)推進，得到了最多使用 個守衛(wèi)就可以全覆蓋的下界法焰。
然而在三維中秧荆，即使每個頂點都放置一個守衛(wèi)，依然存在一種多面體埃仪，使得某些位置無法被覆蓋乙濒。
一個著名的例子是 。

改進

在這里介紹的三角剖分算法總的時間復雜度為 卵蛉。算法復雜度的瓶頸在于排序颁股。
實際上， 年 （永遠滴神） 提出了更加優(yōu)秀的 算法傻丝。
借助隨機化技術(shù)甘有， 提出了 的算法。這種算法基于梯形分解 (trapezoidal decomposition)葡缰，在前面介紹單調(diào)多邊形分解時亏掀，其實已經(jīng)有了梯形分解的雛形。這種算法不僅運行更快而且更為簡單泛释。
最后滤愕， 在 年圓滿地解決了這個問題，他給出了一個線性時間的確定性算法怜校。但是他的論文非臣溆埃晦澀難懂，據(jù)我所知韭畸，可能還沒有人在工業(yè)上使用這個算法宇智。

總結(jié)

本來是一篇筆記，寫著寫著就變得正式了胰丁。。喂分。

這篇文章從美術(shù)館問題入手锦庸，先討論了平面簡單多邊形的覆蓋問題，然后引入三角剖分的概念和其算法蒲祈。介紹了一種時間復雜度 的三角剖分算法甘萧。
算法分為兩部分：單調(diào)多邊形分解和單調(diào)多邊形的三角剖分萝嘁。 描述了算法的大致流程并且給出了部分代碼。
雖然有時間復雜度更低的算法扬卷，但是相差并不特別明顯牙言。本文介紹的算法較為簡單并且能夠大致說明三角剖分算法的主要思想。

參考資料

1. 計算幾何——算法與應用怪得，鄧俊輝譯咱枉，清華大學出版社
2. Polygon Triangulation，Daniel Vlasic徒恋，MIT CSIAL蚕断，http://groups.csail.mit.edu/graphics/classes/6.838/F01/lectures/PolygonTriangulation/
3. 計算幾何第三周：三角剖分（Triangulation），z文聿入挣，https://zhuanlan.zhihu.com/p/33737417
4. Polygon triangulation亿乳，Wikipedia，https://en.wikipedia.org/wiki/Polygon_triangulation