第三百九十四章 泰森多邊形（計(jì)算）

　　荷蘭氣候?qū)W家A·H·Thiessen想測(cè)量大面積的氣候。

　　但是面積太大，需要多個(gè)相距很遠(yuǎn)的氣象站。

　　提出了一種根據(jù)離散分布的氣象站的降雨量來(lái)計(jì)算平均降雨量的方法，即將所有相鄰氣象站連成三角形，作這些三角形各邊的垂直平分線(xiàn)，于是每個(gè)氣象站周?chē)娜舾纱怪逼椒志€(xiàn)便圍成一個(gè)多邊形。

　　用這個(gè)多邊形內(nèi)所包含的一個(gè)唯一氣象站的降雨強(qiáng)度來(lái)表示這個(gè)多邊形區(qū)域內(nèi)的降雨強(qiáng)度，并稱(chēng)這個(gè)多邊形為泰森多邊形。泰森多邊形每個(gè)頂點(diǎn)是每個(gè)三角形的外接圓圓心，泰森多邊形也稱(chēng)為Voronoi圖。

　　泰森多邊形的建立：

　　建立泰森多邊形算法的關(guān)鍵是對(duì)離散數(shù)據(jù)點(diǎn)合理地連成三角網(wǎng)，即構(gòu)建Delaunay三角網(wǎng)。建立泰森多邊形的步驟為：

　　1、離散點(diǎn)自動(dòng)構(gòu)建三角網(wǎng)，即構(gòu)建Delaunay三角網(wǎng)。對(duì)離散點(diǎn)和形成的三角形編號(hào)，記錄每個(gè)三角形是由哪三個(gè)離散點(diǎn)構(gòu)成的。

　　2、找出與每個(gè)離散點(diǎn)相鄰的所有三角形的編號(hào)，并記錄下來(lái)。這只要在已構(gòu)建的三角網(wǎng)中找出具有一個(gè)相同頂點(diǎn)的所有三角形即可。

　　3、對(duì)與每個(gè)離散點(diǎn)相鄰的三角形按順時(shí)針或逆時(shí)針?lè)较蚺判?，以便下一步連接生成泰森多邊形。設(shè)離散點(diǎn)為o。找出以o為頂點(diǎn)的一個(gè)三角形，設(shè)為A；取三角形A除o以外的另一頂點(diǎn)，設(shè)為a，則另一個(gè)頂點(diǎn)也可找出，即為f；則下一個(gè)三角形必然是以of為邊的，即為三角形F；三角形F的另一頂點(diǎn)為e，則下一三角形是以oe為邊的；如此重復(fù)進(jìn)行，直到回到oa邊。

　　4、計(jì)算每個(gè)三角形的外接圓圓心，并記錄之。

　　5、根據(jù)每個(gè)離散點(diǎn)的相鄰三角形，連接這些相鄰三角形的外接圓圓心，即得到泰森多邊形。對(duì)于三角網(wǎng)邊緣的泰森多邊形，可作垂直平分線(xiàn)與圖廓相交，與圖廓一起構(gòu)成泰森多邊形。

　　泰森多邊形的特性是：

　　1，每個(gè)泰森多邊形內(nèi)僅含有一個(gè)離散點(diǎn)數(shù)據(jù)。

　　2，泰森多邊形內(nèi)的點(diǎn)到相應(yīng)離散點(diǎn)的距離最近。

　　3，位于泰森多邊形邊上的點(diǎn)到其兩邊的離散點(diǎn)的距離相等。

　　泰森多邊形可用于定性分析、統(tǒng)計(jì)分析、鄰近分析等。

　　例如，可以用離散點(diǎn)的性質(zhì)來(lái)描述泰森多邊形區(qū)域的性質(zhì)；可用離散點(diǎn)的數(shù)據(jù)來(lái)計(jì)算泰森多邊形區(qū)域的數(shù)據(jù)；判斷一個(gè)離散點(diǎn)與其它哪些離散點(diǎn)相鄰時(shí)，可根據(jù)泰森多邊形直接得出，且若泰森多邊形是n邊形，則就與n個(gè)離散點(diǎn)相鄰；當(dāng)某一數(shù)據(jù)點(diǎn)落入某一泰森多邊形中時(shí)，它與相應(yīng)的離散點(diǎn)最鄰近，無(wú)需計(jì)算距離。