本文是為《Mastering Opencv...》第七章準備的，他要使用主動外觀模型AMM和POSIT算法做一個頭部3D姿态估計。圖像上的特征點由人工标定，但由于頭部運動，比如張嘴，會導緻外觀形狀的扭曲，即特征帶點坐标變化，但相對位置幾乎不變。是以我們要将這些特征點映射到一個穩定的模型上。我們采用Delaunay三角網格。【As the shape we are looking for might be distorted, such as an open mouth for instance, we
are required to map our texture back to a mean shape】
本文内容将首先介紹Delaunay相關概念，然後分别給出OPENCV實作、c代碼實作【改寫自網上，結果似乎有問題】
一、Delaunay三角刨分算法簡介
1.三角刨分定義
三角刨分：假設V是二維實數域上的有限點集，邊e是由點集合V中的點作為端點構成的封閉線段，E為e的集合。那麼，點集V的一個三角刨分T=(V,E)是一個平面圖G，該平面圖滿足條件：
a.除了端點，平面圖中的邊不包含點集中的任何點
b.沒有相交邊
c.平面圖中所有的面都是三角面 ，且所有三角面的合集是散點集V的凸包【用不嚴謹的話來講，給定二維平面上的點集，凸包就是将最外層的點連接配接起來構成的凸多邊型，它能包含點集中所有點的】
2.Delaunay三角刨分定義
Delaunay三角刨分是一種特殊的三角刨分：
a.Delaunay邊：E中的一條邊e(兩個端點為a,b)，滿足條件：存在一個圓經過a,b兩點，圓内(在圓内、圓上最多三點共圓)不包含點集V中其他任何點
b.Delaunay刨分：如果點集V的一個三角刨分T隻包含Delaunay邊，那麼該三角刨分稱為Delaunay刨分
3.Delaunay刨分算法
主要有3種：
a.Lawson算法，首先建立一個大的三角形或多邊形，把所有資料點包圍起來 ，向其中插入一點，該點與包含他的三角形三個點相連，形成3個新 三角形，然後對其逐一進行空外接圓檢測，同時用Lawson設計的局部優化過程LOP進行優化，即通過交換對角線的方法來保證所形成的三角網為Delaunay三角網。
b,Bowyer-Watson算法，The Bowyer–Watson algorithm is an incremental algorithm. It works by adding points, one
具體可查文獻：
c.生長法，待會下文會給出，就是執行效率比較慢：
(1)随機選擇一個起始點A，然後選擇一個離這個點距離最近的點B，構成初始邊，加入邊表；
(2)在剩餘點中選擇一個點作為第三個點C，使得角ACB最大，新生成兩個邊AC和BC加入邊表，并把三角形ABC作為第一個三角形加入三角形表中；
(3)從邊表中取出一條邊DE，邊的兩個端點是E和D，設其已在三角形DEF中；邊DE把平面分成兩個半平面，在剩餘的離散點中尋找一個離散點G，它與點F不在邊DE的同一個半平面中，且角DGE最大，把新邊DG和EG加入邊表，把新三角形DGE加入三角形表中；
(4)如果剩餘的離散點表中還有點，則轉至(3)，否則算法結束。
二、具體實作：
測試的三點集資料，存在txt中，第一行分别表示行數和列列數：
1.opencv版本：
實驗結果：
2.生長法：
Delaunay三角網有一個特性，每個三角網形成的外接圓都不包含其他參考點。利用這一個性質，我們可以直接構成Delaunay三角網：
(1).建立第一個三角形
a.判斷用來建立TIN的總腳點數，小于3則報錯退出。
b.第一點的選擇：連結清單的第一節點，命名為Pt1;
c.第二點的選擇，命名為Pt2，條件1：非Pt1點；條件2：B.距Pt1最近；
d.第三點的選擇，命名為Pt3，條件1：非Pt1，Pt2點；條件2：與Pt1，Pt2點組成的三角形的外接圓内無其他節點；條件3：與Pt1，Pt2組成的三角形中的角∠Pt1Pt3Pt2最大。
e.生成三邊，加入邊表
f.生成第一個三角形，組建三角形表
(2).擴充TIN
a.從邊表頭取一邊，要求：該邊flag标志為假（隻在一個三角形中）
b.從點連結清單中搜尋一點，要求：條件1：與邊中的Pixel3在邊的異側；條件2：該點與邊組成的三角形的外接圓内無其他點；條件3：滿足上面兩條件的點中角Pt1Pt3Pt2最大的點為Pt3。
c.判斷新生成的邊，如果邊表中沒有，則加入邊表尾，設定标志flag為假，如果有，則設定該邊flag為真。
d.将生成的三角形假如三角形表
e.設定選中的邊的标志flag為真
f.轉至a，直至邊表邊的标志flag全部為真。
代碼，主體部分改編自csdn論壇某篇文章，都是連結清單操作。。。
居然畫成這樣，我也很無語。。。但是生長法還是很好實作的，具體論文什麼的，自己去中國智網搜吧