1、DELAUNAY三角網(wǎng)的算法,一、引言 TIN（Triangulated Irregular Network,不規(guī)則三角網(wǎng)） 是由Peuker和他的同事于1978年設(shè)計的一個系統(tǒng)，它是根據(jù)區(qū)域的有限個點集將區(qū)域劃分為相等的三角面網(wǎng)絡(luò)，數(shù)字高程由連續(xù)的三角面組成，三角面的形狀和大小取決于不規(guī)則分布的測點的密度和位置，能夠避免地形平坦時的數(shù)據(jù)冗余，又能按地形特征點表示數(shù)字高程特征。TIN常用來擬合連續(xù)分布現(xiàn)象的覆蓋表面。,二、Delaunay（德洛內(nèi)）三角網(wǎng) 1、定義：一系列相連但不重疊的三角形的集合，而且 這些三角形的外接圓不包含這個面域的其他人任何點。 2、性質(zhì)：（1）、每個Delaunay三

2、角形的外接圓不包含面內(nèi)其他任何點，即Delaunay三角網(wǎng)的空外接圓性質(zhì)。這是創(chuàng)建Delaunay三角網(wǎng)的一項判別標(biāo)準(zhǔn)。 （2）、在由點集V中所能形成的三角網(wǎng)中，Delaunay三角網(wǎng)中三角形的最小角度是最大的。,3、優(yōu)點：結(jié)構(gòu)良好，數(shù)據(jù)結(jié)構(gòu)簡單，數(shù)據(jù)冗余度小，存儲效率高，可適應(yīng)各種分布密度的數(shù)據(jù)。,三、Voronoi圖 （泰森多邊形或Dirichlet圖） 由一組由連接兩鄰點直線的垂直平分線組成的連續(xù)多邊形組成。 N個在平面上有區(qū)別的點，按照最鄰近原則劃分平面；每個點與它的最近鄰區(qū)域相關(guān)聯(lián)。 Delaunay三角形是由與相鄰Voronoi多邊形共享一條邊的相關(guān)點連接而成的三角形。 Delau

3、nay三角形的外接圓圓心是與三角形相關(guān)的Voronoi多邊形的一個頂點。 Voronoi三角形是Delaunay圖的偶圖 。,四、算法 1、分割歸并法 2、逐點插入算法 3、三角網(wǎng)增長法 逐點插入法： 1、遍歷所有散點，求出點集的包容盒，得到作為點集凸殼的初始三角形并放入三角形鏈表。 2、將點集中的散點依次插入，在三角形鏈表中找出其外接圓包含插入點的三角形（稱為該點的影響三角形），刪除影響三角形的公共邊，將插入點同影響三角形的全部頂點連接起來，從而完成一個點在Delaunay三角形鏈表中的插入。,3、根據(jù)優(yōu)化準(zhǔn)則對局部新形成的三角形進(jìn)行優(yōu)化（如互換對角線等）。將形成的三角形放入Delaunay

4、三角形鏈表。 4、循環(huán)執(zhí)行上述第2步，直到所有散點插入完畢。 上述基于散點的構(gòu)網(wǎng)算法理論嚴(yán)密、唯一性好，網(wǎng)格滿足空圓特性，較為理想。由其逐點插入的構(gòu)網(wǎng)過程可知，在完成構(gòu)網(wǎng)后，增加新點時，無需對所有的點進(jìn)行重新構(gòu)網(wǎng)，只需對新點的影響三角形范圍進(jìn)行局部聯(lián)網(wǎng)，且局部聯(lián)網(wǎng)的方法簡單易行。同樣，點的刪除、移動也可快速動態(tài)地進(jìn)行。 但在實際應(yīng)用當(dāng)中，這種構(gòu)網(wǎng)算法不易引入地面的地性線和特征線，當(dāng)點集較大時構(gòu)網(wǎng)速度也較慢，如果點集范圍是非凸區(qū)域或者存在內(nèi)環(huán)，則會產(chǎn)生非法三角形。,為了克服基于散點構(gòu)網(wǎng)算法的上述缺點，特別是為了提高算法效率，可以對網(wǎng)格中三角形的空圓特性稍加放松，亦即采用基于邊的構(gòu)網(wǎng)方法，其算法簡述如下： 1、根據(jù)已有的地性線和特征線，形成控制邊鏈表。 2、以控制邊鏈表中一線段為基邊，從點集中找出同該基邊兩端點距離和最小的點，以該點為頂點，以該基邊為邊，向外擴(kuò)展一個三角形（僅滿足空橢圓特性）并放入三角形鏈表。 3、按照上述第2步，對控制邊鏈表所有的線段進(jìn)行循環(huán)，分別向外擴(kuò)展。,4、依次將新形