分治插入整合算法課件

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

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

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

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

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

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

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

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