一種基于Dijkstra算法的三角網(wǎng)格地表模型算法

1、 目錄一、班級(jí)建設(shè)文化型班級(jí) 14二、班級(jí)文化建設(shè)之基礎(chǔ) 56班級(jí)精神團(tuán)結(jié)、友愛(ài)、感恩、勵(lì)志班訓(xùn)“盡心盡力,盡善盡美”班歌愛(ài)因?yàn)樵谛闹腥⒃绮傥幕瘜儆谖覀兊挠⒆孙S爽 79四、教室文化我們的夢(mèng)將之裝飾 1017五、班級(jí)活動(dòng)文化我們的共同創(chuàng)造 1823江西科學(xué)JIANGXISCIENCEVol29No3Jun2011文章編號(hào):10013679(201103038704一種基于Dijkstra 算法的三角網(wǎng)格地表模型算法謝璞,黎敬濤(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院,云南昆明650000摘要:對(duì)二維地表模型運(yùn)用Dijkstra 算法求解最短路徑時(shí),為了減少計(jì)算量,需要對(duì)模型進(jìn)行簡(jiǎn)化后,才開始進(jìn)行Di

2、jkstra 算法的求解,所以結(jié)果并不符合實(shí)際地表情況。不在模型上進(jìn)行任何簡(jiǎn)化,而是直接在模型上劃分三角網(wǎng)格來(lái)處理最原始的模型。然后用基于Dijkstra 算法和矢量夾角的三角網(wǎng)格地表模型算法求解最短路徑。通過(guò)此算法完成了一個(gè)實(shí)例的最短路徑求解。結(jié)果表明,采用文中算法所得到的結(jié)果符合Dijkstra 算法求得的路徑和實(shí)際情況,而復(fù)雜度并沒(méi)有因?yàn)槲春?jiǎn)化模型而大幅上升,并且算法具有效率高、復(fù)雜度低、穩(wěn)定性好等優(yōu)點(diǎn)。關(guān)鍵詞:三角網(wǎng)格地表模型算法;Dijkstra ;三維網(wǎng)格;矢量夾角中圖分類號(hào):TP3016文獻(xiàn)標(biāo)識(shí)碼:AA Triangular Mesh Surface Model Algorith

3、m Based on Dijkstra AlgorithmXIE Pu ,LI Jing-tao(Institute of Information Engineering and Automation ,Kunming University of Science and Technology ,Yunnan Kunming 650000PRC Abstract :The use of two-dimensional surface model of the Dijkstra shortest path algorithm ,in order to reduce the computationa

4、l load ,the need for simplified models before starting the Dijkstra algorithm to solve ,so the results are not consistent with the actual ground situationThe paper does not make any simplified model ,but directly divide triangular mesh on model to deal with the most primitive of the modelThen ,use t

5、riangular mesh surface model algorithm which based on Dijkstra algorithm and vector angle to solve the shortest pathIn the paper ,an instance of the shortest path solution is com-pleted by the algorithmThe results show that this algorithm is consistent with the results obtained the path obtained by

6、Dijkstra algorithm and the actual situation ,and the complexity of the algorithm is not significantly increased because of no simplificatication ,and the algorithm have the benefit of high efficiency ,complex low ,stable and so noKey words :Triangular mesh surface model algorithm ,Dijkstra ,3d mesh

7、,Vector angle0引言三維網(wǎng)格地表模型算法是在實(shí)際地表模型下尋找最短路徑一種算法,它能夠比較準(zhǔn)確的找到地表模型上的最短路徑,且不用再進(jìn)行優(yōu)化,就已組織的各種活動(dòng)中,我班同學(xué)代表積極參與,并且大多獲得了不錯(cuò)的成績(jī)。以下就是我們班取得的部分榮譽(yù):在院學(xué)風(fēng)建設(shè)月中,我班表現(xiàn)的較突出,被授予精神文明班級(jí);在院船舶杯辯論賽中,我班選手表現(xiàn)優(yōu)異,授予優(yōu)秀獎(jiǎng);在院舉行的一年一次的船舶杯籃球賽中,我班勇獲前四,授予精神文明班級(jí);在每月一次寢室的紅白榜評(píng)定時(shí),我班的寢室每次都有上紅榜的,還有好幾次班上的5個(gè)寢室全部上榜,更素有文明寢室之稱。不足方面在看到進(jìn)步的同時(shí),我們也發(fā)現(xiàn)諸多的不足,主要表現(xiàn)在以下

8、幾個(gè)方面:一、極少數(shù)同學(xué)在學(xué)習(xí)態(tài)度上暴露了不足,偶爾上課遲到或曠課,對(duì)于某些課程的學(xué)習(xí)積極性不高,課下自主學(xué)習(xí)意識(shí)不強(qiáng),成績(jī)不是很理想。二、有些同學(xué)較容易沉迷于網(wǎng)絡(luò),影響了正常的學(xué)習(xí)生活作息時(shí)間。邊界點(diǎn)存入最短距離已知的頂點(diǎn)集合Vknown。擴(kuò)展R邊界,計(jì)算R區(qū)域的所有外邊界ei右側(cè)三角形t中的對(duì)頂點(diǎn)vi 到s的距離,取最短距離對(duì)應(yīng)的vj加入已知最短距離頂點(diǎn)集合Vknown中,將ti加入R區(qū)域內(nèi),同時(shí)修改R區(qū)域的外邊界。每次R區(qū)域外邊界循環(huán)一遍加入一個(gè)未知頂點(diǎn),直到終點(diǎn)(假設(shè)為t點(diǎn)加入。從該算法的思想中可以看到,細(xì)分程度是決定該算法所得結(jié)果是否準(zhǔn)確的關(guān)鍵,細(xì)分程度越高,結(jié)果越準(zhǔn)確,但同時(shí)算法的

9、復(fù)雜度也會(huì)越高1。當(dāng)障礙物數(shù)量較少,從而頂點(diǎn)數(shù)也較少時(shí),模型也較小,類似這種算法效率也較高;但如果障礙物數(shù)量較多,或障礙物邊界復(fù)雜,模型就會(huì)變得很大,因而搜索過(guò)程也會(huì)變得漫長(zhǎng)2。文中把此算法與二維地表模型中的Dijkstra 算法結(jié)合,并引入矢量夾角3,讓最終的路徑能夠既是最短路徑,又能很好的符合地表實(shí)際情況。1基于Dijkstra算法的三角網(wǎng)格地表模型算法由大量小三角平面片組成的三角網(wǎng)格在幾何建模、計(jì)算機(jī)圖形學(xué)、地理信息系統(tǒng)等領(lǐng)域中常用于對(duì)復(fù)雜曲面模型的表示。隨著測(cè)量技術(shù)以及基于測(cè)量數(shù)據(jù)的幾何建模技術(shù)的發(fā)展,人們可以方便地獲得具有豐富細(xì)節(jié)特征的三角網(wǎng)格模型4。正是鑒于以上優(yōu)點(diǎn),文中采用三角網(wǎng)

10、格來(lái)劃分模型?；贒ijkstra算法的三角網(wǎng)格地表模型算法,采用三維網(wǎng)格算法分割地表模型的方法,分割二維的地表模型。采用Dijkstra算法和三維網(wǎng)格地表模型算法分別對(duì)分割好的模型求解最短路徑,綜合2種結(jié)果,得到符合地表模型的最短路徑。所用算法具體描述如下。Step1:模型初始化。將實(shí)際地圖上的各種障礙物看做不規(guī)則的多邊形來(lái)處理,把每個(gè)多邊形的每一個(gè)頂點(diǎn)看作是模型中的一個(gè)節(jié)點(diǎn),并連接這些節(jié)點(diǎn)(除開多邊形內(nèi)部的。Step2:三角網(wǎng)格分割地表模型。在原始模型上不做任何簡(jiǎn)化,連接出新的邊,產(chǎn)生新的三角形,使地表模型的網(wǎng)絡(luò)三角網(wǎng)格化。Step3:對(duì)已經(jīng)分割成三角網(wǎng)格的地表模型采用Dijkstra算法

11、進(jìn)行最短路徑的求解,保存路徑結(jié)果集合,設(shè)為P。Step4:采用三維網(wǎng)格地表模型算法,并運(yùn)用矢量夾角的運(yùn)算結(jié)果來(lái)進(jìn)行路徑選擇,對(duì)三角網(wǎng)格模型再次求解出一個(gè)最短路徑,同樣保存該路徑結(jié)果結(jié)合,設(shè)為Q。Step5:分段比較集合P、Q中的最短路徑節(jié)點(diǎn),將距離較短的路徑節(jié)點(diǎn)保存到新的集合,將這個(gè)集合設(shè)為N。Step6:結(jié)合模型檢查上一步中所得集合N中的節(jié)點(diǎn)是否完全符合實(shí)際地表情況,將其中一些迂回的路徑改為直線。Step7:得到最終的最短路徑集合N*。算法結(jié)束。2應(yīng)用示例21基本假設(shè)求解如圖1所示地表模型A點(diǎn)到B點(diǎn)的最短路徑,圖中各種多邊形代表的是各種障礙物,人是無(wú)法逾越過(guò)去的,只能繞開這些地方,同時(shí)所選擇

12、的路線不能越過(guò)最外層的障礙物 。圖1實(shí)際地表模型通過(guò)算法的1,2步后,可以得到初始化好的三角網(wǎng)格化的地表模型,如圖2 。圖2初始三角網(wǎng)格化地表模型現(xiàn)在的問(wèn)題變成了,如何在不做任何簡(jiǎn)化的三角網(wǎng)格化地表模型上求解出從A點(diǎn)到達(dá)B點(diǎn)的最短路線。·883·江西科學(xué)2011年第29卷22Dijkstra 算法的操作假設(shè)各節(jié)點(diǎn)間的距離矩陣cost ,按照傳統(tǒng)的Dijkstra 算法5,6,來(lái)進(jìn)行一次最短路徑的求解。設(shè)無(wú)向圖G =(V ,E ,其中V =1,2,3,24,25,cost 已經(jīng)給出。設(shè)S 是一個(gè)集合,其中每一個(gè)元素表示一個(gè)節(jié)點(diǎn),初始化為S =1。用一個(gè)矩陣D 用來(lái)記錄從出發(fā)點(diǎn)

13、到其他各個(gè)節(jié)點(diǎn)當(dāng)前的最短距離,初始化為D =(0,35,25,。從S 之外的節(jié)點(diǎn)集合V S 中選出一個(gè)頂點(diǎn)W ,使得D W 的值最小。于是從出發(fā)點(diǎn)到達(dá)W 只通過(guò)S 中的節(jié)點(diǎn),把W 加入到集合S 中,并調(diào)整D 中記錄的從出發(fā)點(diǎn)到V S 中每個(gè)節(jié)點(diǎn)V 的距離:從原來(lái)的D V 和D W +D W V 中選擇較小的值作為新的D V 。重復(fù)上述過(guò)程,直到S 中包含V 中其余各個(gè)節(jié)點(diǎn)的最短路徑。最終矩陣D 就記錄了從出發(fā)點(diǎn)到V 中其余各節(jié)點(diǎn)之間的最短距離。最終,便可得到從A 點(diǎn)到達(dá)B 點(diǎn)的最短路徑,如圖3所示 。圖3Dijkstra 算法得到最短路徑采用Dijkstra 算法得到的A 點(diǎn)到B 點(diǎn)的最短的路

14、徑為P =1,3,7,10,14,16,21,23,25。23三角網(wǎng)格地表模型算法的操作對(duì)同樣的模型采用三角網(wǎng)格地表模型算法再次尋找最短路徑,要說(shuō)明的是在三角網(wǎng)格地表模型算法求解最短路徑的過(guò)程中,所選擇出的路線不一定經(jīng)過(guò)給定的離散點(diǎn)。假設(shè)E (V (i ,V (j 表示以節(jié)點(diǎn)i 和j 為端點(diǎn)的邊,V (i 和V (j 表示節(jié)點(diǎn)i 和節(jié)點(diǎn)j ;Distance (V (i ,V (j 表示V (i 與V (j 之間的直線距離大小;Angle (V (i ,V (j 代表i ,j 這2點(diǎn)之間的路徑與路徑主方向的角度大小,路徑主方向即起點(diǎn)到終點(diǎn)連線所指的方向;集合Q 用來(lái)保存路徑節(jié)點(diǎn)。(1初始化Q

15、=1;(2首先到達(dá)離V (1對(duì)應(yīng)的唯一一條邊E(V (2,V (3所對(duì)應(yīng)的V (7,Q =1,7;(3與V (7所對(duì)應(yīng)的邊是E (V (2,V (6和E (V (6,V (10,由于E (V (2,V (6是障礙物邊界,沒(méi)有對(duì)應(yīng)點(diǎn),而E (V (6,V (10有,所以選擇它對(duì)應(yīng)的節(jié)點(diǎn)V (14加入路徑中,Q =1,7,14;(4加入V (14以后,又有3個(gè)方向選擇,分別是E (V (10,V (15、E (V (15,V (16以及E (V (6,V (13與其垂直線所代表的方向。運(yùn)算得:Angle (V (14,V (1290、Angle (V (14,V (890、Angle (V (14

16、,V (1790;Distance (V (14,V (8=Distance (V (14,V (17Distance (V (14,V (12;對(duì)(1、(2進(jìn)行篩選,得到符合條件的只有V (17,Q =1,7,14,17;(5在V (17所對(duì)應(yīng)的2條邊中,Distance (V (17,E (V (16,V (22Distance (V (17,E (V (18,V (22,將V (21加入最短路徑集合,Q =1,7,14,17,21;(6V (21也和在V (14處的情況一樣,用相同的處理方式,得到加入最短路徑的節(jié)點(diǎn)為V (25,而V (25即為求解的終點(diǎn),故三角網(wǎng)格求解過(guò)程到此結(jié)束。最終

17、的最短路徑集合為Q =(1,7,14,17,21,25 。圖4基于矢量夾角的三角網(wǎng)格算法得到的最短路徑24最終最短路徑的確定現(xiàn)在用2種算法得到了2條最短路徑,分別是Dijkstra 算法得到的最短路徑集合P =(1,3,7,10,14,16,21,23,25和三角網(wǎng)格地表模型算法得到的最短路徑集合Q =(1,7,14,17,21,25。設(shè)Distancofpath (V (i ,V (j ,V (k 代表了從V (i 經(jīng)V (j 等節(jié)點(diǎn)到達(dá)V (k 時(shí)所走的路徑長(zhǎng)度。為了確定最終的最短路徑節(jié)點(diǎn)集合N ,對(duì)集合P 、Q 進(jìn)行分段對(duì)比選取:·983·第3期謝璞等:一種基于Dij

18、kstra 算法的三角網(wǎng)格地表模型算法(1對(duì)比從V (1到V (7的2條路徑,Distan-ceofpath (V (1,V (7Distanceofpath (V (1,V (3、V (7,N =1,7;(2對(duì)比從V (7到V (14的2條路徑,Dis-tanceofpath (V (7,V (14Distanceofpath (V (7,V (10、V (14,N =1,7,14;(3對(duì)比從V (14到V (21的2條路徑,Dis-tanceofpath (V (14,V (16,V (21Distanceof-path (V (14,V (17、V (21,N =1,7,14,16,21;(4對(duì)比從V (21到V (25的2條路徑,Dis-tanceofpath (V (21,V (25Distanceofpath (V (21,V (23、V (25,N =1,7,14,16,21,25;通過(guò)一系列算法,得到了基于Dijkstra 算法三維網(wǎng)格地表模型算法的最短路徑節(jié)點(diǎn)集合N =1,7,14,16,21,25,如圖5所示 。圖5綜合2種算法得到的最短路徑3結(jié)束語(yǔ)本文針對(duì)不做簡(jiǎn)化