三角化

在使用OpenGL畫圖的過程中，由於OpenGL不支持直接繪製凹多邊形，所以我們通常需要先將凹多邊形轉化為一組三角形下面就是一個三角化多邊形的算法

1、 用單向循環鏈表保存多邊形頂點,並計算這個鏈表中每一個頂點的凸凹性。

2、在循環鏈表中順序取三個結點P、Q、R ,如果Q 為凸點,並且由P、Q、R 所構成的三角形PQR不包含多邊形上其他頂點,則計算△PQR 的特徵角(三角形內最小的角)。求出所有這樣的三角形,從中選擇特徵角最大的△PQR ,保存該三角形,並從鏈表中刪去結點Q。

3、如果鏈表中存在三個以上頂點,則轉步驟2。

4、由鏈表中的最後三個頂點構成一個三角形。