1、分治插入整合算法 評價一個算法的優劣關鍵在于其對地形表達的近似程度即數學精度和時間效率以及其占用系統資源的多少，前面敘述的各種算法在這些方面均各有利弊，比如，分治算法由于其數據的分塊處理，大大地減少了每次數據遍歷的搜索量，因而其時效性非常好，但由于是遞歸執行，需要較大的內存空間，占用較多的系統資源;與些相反，逐點插入法則比較容易實現，占用內存少，但其時效性差。為此人們也種提出過結合各種算法優點的相關算法，如文獻武曉波，王世新，肖春生.Delaunay三角網的生成算法研究(J).測繪學報1999.2提出的合成算法等。在對各種算法深入研究的基礎上，本文提出并實現了一種在數據分塊基礎上，逐點插入的算

2、法，兼顧了分治算法和逐點插入算法的長處，經實驗驗證，取得了良好的效果，并將此算法命名為分治插入整合算法。1算法的基本過程一、數據集的分塊(劃分子集) 二、各子集Vi中三角網的構建三、所有子塊的整合b.子集Vi中數據點的數量的確定及子集Vi的劃分可以在程序中規定或以人機交互方式確定各子集Vi所含的點數的最大值Pmax和最小值Pmin,在系統應用N 的開方(N為總點數)來確定并輸入Vi中允許點數的最大Pmax和最小Pmin,將數據集V分成點數近似相等的i個子集Vi (i=1, 2,，n)。二、各子集Vi中三角網的構建1、構建第一個三角形2、逐點插入生成新的三角形3、新生三角形的LOP優化4、其它子

3、集構建初始三角網其數據結構如圖。圖表中的“一”表示某點對邊所對應的三角形不存在，即其對邊為子三角網的凸殼邊。數據的結構共有三個部分。 第一部分記錄了采樣點的數量(FEATPOINTS)和各點的點號、平面坐標及高程值。 第二部分是三角網的拓撲結構，包含每一三角形的標識、順時針組成該三角形的3個頂點點號，及與各頂點對邊相鄰三角形的標識號。數據結構簡單，但清晰地記錄了三角形的頂點、邊以及與相鄰三角形的關系，并隱式地記錄了組成此三角形的各邊。通過對各頂點的對邊三角形的標識號的記錄，完整描述了三角網中三角形間的拓撲關系，便于數據處理。第三部分記錄了一條(隨機的)外凸殼上的邊，如:OUTESTTRI=T2

4、 -6062, 3,表示標識號為T2-26062的三角形的第三個頂點的對邊為外凸殼邊。由于三角形的點號記錄順序均是順時針的，因此，通過記錄凸殼上的一條邊就可以找到凸殼上的所有邊。這樣就便于新點的內插和子三角網的合并。 外凸殼上的邊的記錄便于快速搜索，如不記錄，也可通過對三角網進行遍歷找出第一個凸殼邊，但顯然降低了程序運行的效率。建立初始三角網(第一個三角形)時，凸殼邊記錄該三角形的任意一邊。2、逐點插入生成新的三角形三角形內點的插入三角形外點的插入新生成的三角形與其共邊三角形的LOP優化重復以上步驟，直至該子集Vi中所有的點均插入完畢，即構成了該子集Vi的三角網外凸殼上通視點的搜索 三角形內點

5、的插入 在子集中依次取一個新的插入點，首先查找所取的新插入點i所在的三角形。如果i位于一三角形內，則分別連接i與此三角形的三頂點將該三角形一分為三(如圖2. 6所示)，標識3個新三角形，并按順時針方向分別記錄各三角形的三頂點的點號;將所在原三角形的拓撲關系傳遞給新三角形;依次對新三角形作與共邊三角形的可能存在的LOP優化;去除三角網中的原三角形。新生成的三角形與其共邊三角形的LOP優化接著對以對應的原外凸殼邊如ba, cb, do和ed為公共邊的各對三角形進行LOP優化以獲得最佳形狀的三角形。在和的LOP優化過程中，優化會生成新的三角形，新三角形將繼續與共邊三角形進行LOP優化，直到不能再優化

6、為止。重復以上步驟，直至該子集Vi中所有的點均插入完畢，即構成了該子集Vi的三角網。外凸殼上通視點的搜索如前所述，外凸殼邊都是順時針記錄的，從圖2 .7可看出，與外插點i通視的點所生成的新三角形均為順時針的，如a iba, a icb, a ied，判定三角形點序的時針方向以代數面積計算法確定。而外插點1與不通視的點構成三角形后，為逆時針方向的，如a iaf，該三角形不能作為新三角形加入到三角網中。 此時三角形的面積為:3、新生三角形的LOP優化其原理就是根據D一三角網的性質對具有公共邊的三角形組成的四邊形進行判別，如果其中的某三角形的外接圓包含該四邊形的第四個頂點，則將該四邊形的對角線交換，

7、生成以另一條對角線為公共邊的兩個三角形。此時一定滿足空圓性質，得到D一三角形。同時對TIN的數據記錄進行更新，增添新的三角形標識號記錄及其對應的頂點和頂點的對邊三角形，刪除被廢棄的三角形。4、其它子集構建初始三角網重復上述步驟1,2,3，對各子集構建三角網。此時每一三角網均是凸殼的。三、所有子塊的整合1、確定相鄰兩個子三角網的外凸殼的下底線 如前所述，各子三角網的外殼為凸殼。凸殼上點和邊均在TIN的數據結構中按順時針方向記錄，搜索凸殼下底線的過程如下。 設SL, SR分別表示左右兩個凸殼。 首先在左凸殼SL上任取一凸殼點，按上述三角形面積判定法找出右凸殼上的第一條通視邊的第一個凸殼點。若無通視

8、邊，則在SL上順時針取下一點再作搜索判斷，直到找到通視邊。 以右凸殼SR上剛找到的點仍按面積判定法搜索左凸殼SL上最后一條通視邊的第二個凸殼點。 重復以上兩個步驟，在SL和SR上循環搜索，直到從SL上的凸殼點不再能找到SR上的通視邊，目從SR上的凸殼點也不再能找到SL上的通視邊。 此時，連接在SL和SR上分別找到的最后的凸殼點，所連線即為左右凸殼的下底線。如圖2. 10中的ac。2、相鄰兩個子三角網的合并 找到左右兩個了三角網的下底線后如圖(ac)中的，就可從下底線ac開始向上分別在SL上找到a的上一個凸殼點b，在SR上找到c的下一個凸殼點d。對四邊形acdb通過LOP優化新生兩個三角形 abc和bdc。 將