GIS和地理分析中經(jīng)常采用泰森多邊形進(jìn)行快速插值，和分析地理實(shí)體的影響區(qū)域，是解決鄰接度問題的又一常用工具。

一、泰森多邊形及其特性

    荷蘭氣候?qū)W家A·H·Thiessen提出了一種根據(jù)離散分布的氣象站的降雨量來計(jì)算平均降雨量的方法，即將所有相鄰氣象站連成三角形，作這些三角形各邊的垂直平分線，于是每個(gè)氣象站周圍的若干垂直平分線便圍成一個(gè)多邊形。用這個(gè)多邊形內(nèi)所包含的一個(gè)唯一氣象站的降雨強(qiáng)度來表示這個(gè)多邊形區(qū)域內(nèi)的降雨強(qiáng)度，并稱這個(gè)多邊形為泰森多邊形。如圖5-6-1，其中虛線構(gòu)成的多邊形就是泰森多邊形。泰森多邊形每個(gè)頂點(diǎn)是每個(gè)三角形的外接圓圓心。泰森多邊形也稱為Voronoi圖，或dirichlet圖。

圖5-6-1 泰森多邊形

    泰森多邊形的特性是：

    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ì)來描述泰森多邊形區(qū)域的性質(zhì)；可用離散點(diǎn)的數(shù)據(jù)來計(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)最鄰近，無需計(jì)算距離。

    在泰森多邊形的構(gòu)建中，首先要將離散點(diǎn)構(gòu)成三角網(wǎng)。這種三角網(wǎng)稱為Delaunay三角網(wǎng)。

二、Delaulay三角形的構(gòu)建

    概要介紹Delaunay三角形的構(gòu)建、產(chǎn)生的準(zhǔn)則后，具體講述凸包插值算法生成Delaunay三角網(wǎng)的步驟：
    1、凸包生成；
    2、環(huán)切邊界法凸包三角剖分；
    3、離散點(diǎn)內(nèi)插。

     Delaunay三角網(wǎng)的構(gòu)建也稱為不規(guī)則三角網(wǎng)的構(gòu)建，就是由離散數(shù)據(jù)點(diǎn)構(gòu)建三角網(wǎng)，如圖5-6-2，即確定哪三個(gè)數(shù)據(jù)點(diǎn)構(gòu)成一個(gè)三角形，也稱為自動(dòng)聯(lián)接三角網(wǎng)。即對(duì)于平面上n個(gè)離散點(diǎn)，其平面坐標(biāo)為(x_i，y_i)，i＝1，2，…，n，將其中相近的三點(diǎn)構(gòu)成最佳三角形，使每個(gè)離散點(diǎn)都成為三角形的頂點(diǎn)。  

圖5-6-2 Delaunay三角網(wǎng)

    自動(dòng)聯(lián)接三角網(wǎng)的結(jié)果為所有三角形的三個(gè)頂點(diǎn)的標(biāo)號(hào)，如：

                         1,   2，  8

                         2,   8，  3

                         3,   8，  7

                             ┇

為了獲得最佳三角形，在構(gòu)三角網(wǎng)時(shí)，應(yīng)盡可能使三角形的三內(nèi)角均成銳角，即符合Delaunay三角形產(chǎn)生的準(zhǔn)則：

    1、任何一個(gè)Delaunay三角形的外接圓內(nèi)不能包含任何其它離散點(diǎn)。

    2、 相鄰兩個(gè)Delaunay三角形構(gòu)成凸四邊形，在交換凸四邊形的對(duì)角線之后，六個(gè)內(nèi)角的最小者不再增大。該性質(zhì)即為最小角最大準(zhǔn)則。

圖5-6-3 凸包

    下面介紹Tsai（1993）提出的在n維歐拉空間中構(gòu)造Delaunay三角形的通用算法---凸包插值算法。

（一）、凸包生成

1、求出點(diǎn)集中滿足min(x-y)、min(x+y)、max(x-y)、max(x+y)的四個(gè)點(diǎn)，并按逆時(shí)針方向組成一個(gè)點(diǎn)的鏈表。這4個(gè)點(diǎn)是離散點(diǎn)中與包含離散點(diǎn)的外接矩形的4個(gè)角點(diǎn)最近的點(diǎn)。這4個(gè)點(diǎn)構(gòu)成的多邊形作為初始凸包。

2、對(duì)于每個(gè)凸包上的點(diǎn)I，設(shè)它的后續(xù)點(diǎn)為J，計(jì)算矢量線段IJ右側(cè)的所有點(diǎn)到IJ的距離，求出距離最大的點(diǎn)K。

3、將K插入I、J之間，并將K賦給J。

4、重復(fù)2、3步，直到點(diǎn)集中沒有在線段IJ右側(cè)的點(diǎn)為止。

5、將J賦給I，J取其后續(xù)點(diǎn)，重復(fù)2、3、4步。

6、當(dāng)凸包中任意相鄰兩點(diǎn)連線的右側(cè)不存在離散點(diǎn)時(shí)，結(jié)束點(diǎn)集凸包求取過程。

完成這一步后，形成了包含所有離散點(diǎn)的多邊形（凸包），如圖5-6-3所示。

（二）、環(huán)切邊界法凸包三角剖分

在凸包鏈表中每次尋找一個(gè)由相鄰兩條凸包邊組成的三角形，在該三角形的內(nèi)部和邊界上都不包含凸包上的任何其它點(diǎn)。將這個(gè)點(diǎn)去掉后得到新的凸包鏈表。重復(fù)這個(gè)過程，直到凸包鏈表中只剩三個(gè)離散點(diǎn)為止。將凸包鏈表中的最后三個(gè)離散點(diǎn)構(gòu)成一個(gè)三角形，結(jié)束凸包三角剖分過程。

圖5-6-4 環(huán)切邊界法凸包三角剖分

    完成這一步后，將凸包中的點(diǎn)構(gòu)成了若干Delaunay三角形，如圖5-6-4所示。

（三）、離散點(diǎn)內(nèi)插

    在對(duì)凸包進(jìn)行三角剖分之后，不在凸包上的其余離散點(diǎn)，可采用逐點(diǎn)內(nèi)插的方法進(jìn)行剖分。基本過程為：

1、找出外接圓包含待插入點(diǎn)的所有三角形，構(gòu)成插入?yún)^(qū)域。

2、刪除插入?yún)^(qū)域內(nèi)的三角形公共邊，形成由影響三角形頂點(diǎn)構(gòu)成的多邊形。

3、將插入點(diǎn)與多邊形所有頂點(diǎn)相連，構(gòu)成新的Delaunay三角形。

4、重復(fù)1、2、3，直到所有非凸殼離散點(diǎn)都插入完為止。
完成這一步后，就完成了Delaunay三角網(wǎng)的構(gòu)建，如圖5-6-5所示。

圖5-6-5 離散點(diǎn)內(nèi)插

三、泰森多邊形的建立步驟

    建立泰森多邊形算法的關(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)，并記錄下來。這只要在已構(gòu)建的三角網(wǎng)中找出具有一個(gè)相同頂點(diǎn)的所有三角形即可。

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

    3、對(duì)與每個(gè)離散點(diǎn)相鄰的三角形按順時(shí)針或逆時(shí)針方向排序，以便下一步連接生成泰森多邊形。排序的方法可如圖5-6-6所示。設(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)邊緣的泰森多邊形，可作垂直平分線與圖廓相交，與圖廓一起構(gòu)成泰森多邊形。