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

1、 目錄一、班級建設(shè)文化型班級 14二、班級文化建設(shè)之基礎(chǔ) 56班級精神團結(jié)、友愛、感恩、勵志班訓(xùn)“盡心盡力,盡善盡美”班歌愛因為在心中三、早操文化屬于我們的英姿颯爽 79四、教室文化我們的夢將之裝飾 1017五、班級活動文化我們的共同創(chuàng)造 1823江西科學(xué)JIANGXISCIENCEVol29No3Jun2011文章編號:10013679(201103038704一種基于Dijkstra 算法的三角網(wǎng)格地表模型算法謝璞,黎敬濤(昆明理工大學(xué)信息工程與自動化學(xué)院,云南昆明650000摘要:對二維地表模型運用Dijkstra 算法求解最短路徑時,為了減少計算量,需要對模型進行簡化后,才開始進行Di

2、jkstra 算法的求解,所以結(jié)果并不符合實際地表情況。不在模型上進行任何簡化,而是直接在模型上劃分三角網(wǎng)格來處理最原始的模型。然后用基于Dijkstra 算法和矢量夾角的三角網(wǎng)格地表模型算法求解最短路徑。通過此算法完成了一個實例的最短路徑求解。結(jié)果表明,采用文中算法所得到的結(jié)果符合Dijkstra 算法求得的路徑和實際情況,而復(fù)雜度并沒有因為未簡化模型而大幅上升,并且算法具有效率高、復(fù)雜度低、穩(wěn)定性好等優(yōu)點。關(guān)鍵詞:三角網(wǎng)格地表模型算法;Dijkstra ;三維網(wǎng)格;矢量夾角中圖分類號:TP3016文獻標(biāo)識碼: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)格地表模型算法是在實際地表模型下尋找最短路徑一種算法,它能夠比較準(zhǔn)確的找到地表模型上的最短路徑,且不用再進行優(yōu)化,就已組織的各種活動中,我班同學(xué)代表積極參與,并且大多獲得了不錯的成績。以下就是我們班取得的部分榮譽:在院學(xué)風(fēng)建設(shè)月中,我班表現(xiàn)的較突出,被授予精神文明班級;在院船舶杯辯論賽中,我班選手表現(xiàn)優(yōu)異,授予優(yōu)秀獎;在院舉行的一年一次的船舶杯籃球賽中,我班勇獲前四,授予精神文明班級;在每月一次寢室的紅白榜評定時,我班的寢室每次都有上紅榜的,還有好幾次班上的5個寢室全部上榜,更素有文明寢室之稱。不足方面在看到進步的同時,我們也發(fā)現(xiàn)諸多的不足,主要表現(xiàn)在以下

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

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

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

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

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

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

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

15、=1;(2首先到達離V (1對應(yīng)的唯一一條邊E(V (2,V (3所對應(yīng)的V (7,Q =1,7;(3與V (7所對應(yīng)的邊是E (V (2,V (6和E (V (6,V (10,由于E (V (2,V (6是障礙物邊界,沒有對應(yīng)點,而E (V (6,V (10有,所以選擇它對應(yīng)的節(jié)點V (14加入路徑中,Q =1,7,14;(4加入V (14以后,又有3個方向選擇,分別是E (V (10,V (15、E (V (15,V (16以及E (V (6,V (13與其垂直線所代表的方向。運算得: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;對(1、(2進行篩選,得到符合條件的只有V (17,Q =1,7,14,17;(5在V (17所對應(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é)點為V (25,而V (25即為求解的終點,故三角網(wǎng)格求解過程到此結(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é)點到達V (k 時所走的路徑長度。為了確定最終的最短路徑節(jié)點集合N ,對集合P 、Q 進行分段對比選取:·983·第3期謝璞等:一種基于Dij

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