對論文Triangulation by Ear Clipping 的理解
不涉及帶孔洞的多邊形及多邊形迭代
問就是功能不需要

聲明：在本學(xué)習(xí)筆記的寫作過程中，沒有一只貓貓受到實際傷害甩骏。
（包括賽博貓貓在內(nèi)）

引入

計算機(jī)圖形學(xué)的多邊形分解問題

簡單多邊形定義

定義一個簡單多邊形為由從到的個點(diǎn)組成的有序序列薄翅。兩相鄰頂點(diǎn)之間以邊相連粥谬，且起點(diǎn)和終點(diǎn)之間以邊相連。簡單多邊形的每個頂點(diǎn)有且僅有兩條邊计贰，簡單多邊形的任意兩條邊僅在頂點(diǎn)處相交筷笨。簡單多邊形和復(fù)雜多邊形的對比如圖所示

簡單與復(fù)雜多邊形對比

左側(cè)多邊形為簡單多邊形拐袜。中間的多邊形的頂點(diǎn)1有兩條以上邊冯凹，不為簡單多邊形谎亩。右側(cè)多邊形中連接頂點(diǎn)1和頂點(diǎn)4的邊與其他邊在非頂點(diǎn)處相交，該多邊形不為簡單多邊形谈竿。

在一個簡單多邊形中，當(dāng)遍歷邊緣時摸吠，多邊形內(nèi)部的有限區(qū)域總處于遍歷方向同一側(cè)空凸。假設(shè)以逆時針方向遍歷例圖中的簡單多邊形邊緣，則多邊形內(nèi)部區(qū)域始終處于遍歷方向左側(cè)寸痢。

多邊形三角化算法

將簡單多邊形分解為多個三角形的過程叫做多邊形三角化呀洲。對具有個頂點(diǎn)的任意多邊形進(jìn)行三角化分解都會得到個三角形。在諸多算法中復(fù)雜度為的ear clipping算法算是最簡單又好用的一個啼止，其他復(fù)雜度更低的算法也存在道逗，不過會比ear clipping更難實現(xiàn)。

Ear Clipping算法

下文用貓耳朵指代ear 用咔耳朵算法指代ear clipping）

我覺得論文作者也會贊同的 除了貓奴還有誰會看到三角形就想到尖尖耳朵呢）

定義

貓貓耳朵

多邊形的一只貓貓耳朵是由三個相鄰頂點(diǎn)構(gòu)成的三角形献烦，其中 是三角形凸出的頂點(diǎn)滓窍，在該頂點(diǎn)處三角形的內(nèi)角角度小于。作一條連接點(diǎn)的輔助線巩那，該線段完全位于多邊形內(nèi)部吏夯。這只貓貓耳朵只含有構(gòu)成耳朵的三個頂點(diǎn)，不包含多邊形的其他頂點(diǎn)即横。在計算機(jī)幾何學(xué)術(shù)語里把連接點(diǎn)的輔助線叫做多邊形的一條對角線噪生，把頂點(diǎn)叫做耳朵尖（貓貓的耳朵根根和耳朵尖尖，懂得都懂）东囚。一個三角形就是一只貓貓耳朵跺嗽，三角形的任意一個頂點(diǎn)都可以是耳朵尖尖。

有四條邊及以上的多邊形擁有至少兩只不重疊的耳朵，這就提供給我們一個遞歸實現(xiàn)多邊形三角化的思路桨嫁。若在含有個頂點(diǎn)的多邊形內(nèi)確定并移除一個三角形植兰，移除后的多邊形具有個頂點(diǎn)。重復(fù)該過程瞧甩，即是復(fù)雜度為的三角化算法钉跷。

咔耳朵算法

好消息：咔耳朵算法的復(fù)雜度可以降到

壞消息：難的步驟要來了

step1

首先，將多邊形以雙鏈表形式存儲肚逸，以便快速咔掉耳朵尖尖爷辙。這個步驟的復(fù)雜度是。

step2

其次朦促，對頂點(diǎn)進(jìn)行迭代膝晾，分出各個不重疊的貓貓耳朵。對于每個頂點(diǎn)和該頂點(diǎn)對應(yīng)的三角形务冕，測試多邊形的其他頂點(diǎn)是否位于該三角形中血当。該索引對取模，所以且禀忆。如果三角形內(nèi)不包含多邊形的其他頂點(diǎn) 臊旭，我們就喜提了一只貓貓耳朵！如果三角形內(nèi)至少含有多邊形的一個頂點(diǎn)箩退，它就不是貓貓耳朵离熏。在三角形包容測試中效率更高的三角化方法是只考慮反射點(diǎn)。反射點(diǎn)指由兩條邊構(gòu)成的角度大于的內(nèi)部角的頂點(diǎn)戴涝。多邊形的數(shù)據(jù)結(jié)構(gòu)包含四個同時共用一個存儲數(shù)組的雙鏈表滋戳，而非動態(tài)分配和釋放內(nèi)存的標(biāo)準(zhǔn)列表數(shù)據(jù)結(jié)構(gòu)。使用循環(huán)鏈表存儲多邊形的所有頂點(diǎn)啥刻，線性表存儲凸頂點(diǎn)奸鸯，另一個線性表存儲反射點(diǎn)，另一個循環(huán)鏈表存儲耳朵尖尖可帽。

step3

當(dāng)完成對存儲反射點(diǎn)和耳朵尖尖的數(shù)據(jù)列表初始化后娄涩，就可以一只接一只地咔掉貓貓耳朵了！若是已經(jīng)被咔掉的貓貓耳朵映跟，那么與其相鄰的頂點(diǎn)和頂點(diǎn)的邊的參數(shù)隨之變化钝满。若一相鄰頂點(diǎn)是凸出點(diǎn)，則其仍是凸出點(diǎn)申窘。若一相鄰頂點(diǎn)是耳朵弯蚜，在移除后它可能就不再是耳朵了。若為反射點(diǎn)剃法，則可能變?yōu)橥钩鳇c(diǎn)或耳朵碎捺。在移除后，若存在一凸出的相鄰頂點(diǎn)，則必須通過遍歷反射點(diǎn)和測試三角形內(nèi)是否包含點(diǎn)來驗證該相鄰頂點(diǎn)是否為耳朵收厨。整個過程的復(fù)雜度是

算法示例

以第一張圖的簡單多邊形為例

初始的簡單多邊形

凸出頂點(diǎn)的初始列表為

反射頂點(diǎn)的初始列表為

耳朵尖尖的初始列表為（再復(fù)習(xí)一遍晋柱，耳朵尖尖=這個點(diǎn)是凸出點(diǎn)+和這個點(diǎn)相鄰的兩個點(diǎn)的連線完全在多邊形內(nèi)部）

凸出點(diǎn)
反射點(diǎn)
耳朵尖尖
三角形	暫無

① 把耳朵尖尖對應(yīng)的貓貓耳朵咔掉，那么三角化咔出來的第一個三角形就是诵叁。

咔掉第一個三角形

與相鄰的頂點(diǎn)初始時是反射點(diǎn)雁竞，咔掉后仍是反射點(diǎn)。與相鄰的頂點(diǎn)初始時是耳朵尖尖拧额，咔掉后仍是耳朵尖尖碑诉。可知反射點(diǎn)列表維持原狀侥锦，但耳朵尖尖列表變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=E%20%3D%20%5C%7B4%2C6%2C9%5C%7D" alt="E = \{4,6,9\}" mathimg="1">进栽。

凸出點(diǎn)
反射點(diǎn)
耳朵尖尖
三角形

② 然后把頂點(diǎn)對應(yīng)的耳朵咔掉，可得三角化后的又一個三角形恭垦。

咔掉第二個三角形

與相鄰的頂點(diǎn)初始時是反射點(diǎn)快毛，咔掉后仍是反射點(diǎn)。與相鄰的頂點(diǎn)初始時是反射點(diǎn)番挺，咔掉后變成了凸出點(diǎn)唠帝，經(jīng)過測試后確定為耳朵尖尖，故從反射點(diǎn)列表中移除玄柏，反射點(diǎn)列表變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=R%20%3D%20%5C%7B2%2C7%2C8%5C%7D" alt="R = \{2,7,8\}" mathimg="1">襟衰。但耳朵尖尖列表變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=E%20%3D%20%5C%7B4%2C6%2C9%5C%7D" alt="E = \{4,6,9\}" mathimg="1">。

凸出點(diǎn)
反射點(diǎn)
耳朵尖尖
三角形

如此重復(fù)直到將多邊形全部三角化禁荸，得到三角形

分解后的多邊形