泰森多邊形演算法

Ⅰ 德洛內三角演算法（Delaunay triangulation）基本方法是怎樣的，說的詳細些，另外與三維空間連接性有什麼關

哈哈，剛好做了這道題～感情你也是學測量的？

荷蘭氣候學家A•H•Thiessen提出了一種根據離散分布的氣象站的降雨量來計算平均降雨量的方法，即將所有相鄰氣象站連成三角形，作這些三角形各邊的垂直平分線，於是每個氣象站周圍的若干垂直平分線便圍成一個多邊形。用這個多邊形內所包含的一個唯一氣象站的降雨強度來表示這個多邊形區域內的降雨強度，並稱這個多邊形為泰森多邊形。如圖5-6-1，其中虛線構成的多邊形就是泰森多邊形。泰森多邊形每個頂點是每個三角形的外接圓圓心。泰森多邊形也稱為Voronoi圖，或dirichlet圖。

圖5-6-1泰森多邊形

泰森多邊形的特性是：

1、每個泰森多邊形內僅含有一個離散點數據；

2、泰森多邊形內的點到相應離散點的距離最近；

3、位於泰森多邊形邊上的點到其兩邊的離散點的距離相等。

泰森多邊形可用於定性分析、統計分析、鄰近分析等。例如，可以用離散點的性質來描述泰森多邊形區域的性質；可用離散點的數據來計算泰森多邊形區域的數據；判斷一個離散點與其它哪些離散點相鄰時，可根據泰森多邊形直接得出，且若泰森多邊形是n邊形，則就與n個離散點相鄰；當某一數據點落入某一泰森多邊形中時，它與相應的離散點最鄰近，無需計算距離。

在泰森多邊形的構建中，首先要將離散點構成三角網。這種三角網稱為Delaunay三角網。

對於泰森多邊形（即Delaunay三角網）內的Delaunay三角形的構建方法應為：

1、凸包生成；

2、環切邊界法凸包三角剖分；

3、離散點內插。

Delaunay三角形產生准則的最簡明的形式是：任何一個Delaunay三角形的外接圓的內部不能包含其它任何點。它的最大化最小角原則是：每兩個相鄰的三角形構成的凸四邊形的對角線，在相互交換後，六個內角的最小角不再增大。

而泰森多邊形（即Delaunay三角網）的構建步驟應為：

1、離散點自動構建三角網，即構建Delaunay三角網。對離散點和形成的三角形編號，記錄每個三角形是由哪三個離散點構成的。

2、找出與每個離散點相鄰的所有三角形的編號，並記錄下來。這只要在已構建的三角網中找出具有一個相同頂點的所有三角形即可。

圖5-6-6泰森多邊形的建立

3、對與每個離散點相鄰的三角形按順時針或逆時針方向排序，以便下一步連接生成泰森多邊形。排序的方法可如圖5-6-6所示。設離散點為o。找出以o為頂點的一個三角形，設為A；取三角形A除o以外的另一頂點，設為a，則另一個頂點也可找出，即為f；則下一個三角形必然是以of為邊的，即為三角形F；三角形F的另一頂點為e，則下一三角形是以oe為邊的；如此重復進行，直到回到oa邊。

4、計算每個三角形的外接圓圓心，並記錄之。

5、根據每個離散點的相鄰三角形，連接這些相鄰三角形的外接圓圓心，即得到泰森多邊形。對於三角網邊緣的泰森多邊形，可作垂直平分線與圖廓相交，與圖廓一起構成泰森多邊形。

怎麼只能插入一張圖片啊.......暈.......

Ⅱ 泰森多邊形法的泰森多邊形的建立步驟

建立泰森多邊形演算法的關鍵是對離散數據點合理地連成三角網，即構建Delaunay三角網。建立泰森多邊形的步驟如下：
1、離散點自動構建三角網，即構建Delaunay三角網。對離散點和形成的三角形編號，記錄每個三角形是由哪三個離散點構成的；
2、找出與每個離散點相鄰的所有三角形的編號，並記錄下來。這只要在已構建的三角網中找出具有一個相同頂點的所有三角形即可；
3、對與每個離散點相鄰的三角形按順時針或逆時針方向排序，以便下一步連接生成泰森多邊形。排序的方法可如圖所示。設離散點為o。找出以o為頂點的一個三角形，設為A；取三角形A除o以外的另一頂點，設為a，則另一個頂點也可找出，即為f；則下一個三角形必然是以of為邊的，即為三角形F；三角形F的另一頂點為e，則下一三角形是以oe為邊的；如此重復進行，直到回到oa邊；
4、計算每個三角形的外接圓圓心，並記錄之；
5、根據每個離散點的相鄰三角形，連接這些相鄰三角形的外接圓圓心，即得到泰森多邊形。對於三角網邊緣的泰森多邊形，可作垂直平分線與圖廓相交，與圖廓一起構成泰森多邊形。
參考
泰森多邊形的建立