矢量圖中繞過障礙物的最短路徑算法研究

1、自動(dòng)化技術(shù)與應(yīng)用2003年第22卷第1期計(jì)算機(jī)應(yīng)用矢量圖中繞過障礙物的最短路徑算法研究AlgorithmsForTheShortestPathRoundingObstaclesInVectorGraphics華中科技大學(xué)陳傳波唐浩ChenChuanbo,TangHao摘要:通過比較幾種常見的有障礙物時(shí)求最短路徑的算法,徑的近似算法。關(guān)鍵詞:最短路徑探索線繞障偏移量Abstract:ThispapercomparesseveralpathontheLine-searchingalgorithm,bringsforwardanim2provedalgorithmKewords:TheOffsetf

2、orobstaclerounding中圖分類號(hào):TP11:A文章編號(hào):100327241(2003)01200342031引言運(yùn)輸管理以及工程設(shè)計(jì)的許多方面,如各種工藝路線的安排,電網(wǎng)及管道線網(wǎng)的鋪設(shè),電子地圖的尋路等問題,都與圖的最短路徑問題密切相關(guān)。在某些工程應(yīng)用中,如設(shè)計(jì)電路圖或布線圖時(shí),常常碰到這樣的情況:電路元件和已布好的連接線成為了布線障礙。為了避免新的連接線穿越元器件,就必須按一定的策略使得某些已作好的連接線作出規(guī)避,同時(shí)求出障礙群中兩點(diǎn)間的最短路徑,按這條路徑為新作的連接線布線。降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度。通常求最短路徑是在一個(gè)連通圖中進(jìn)行,各個(gè)節(jié)點(diǎn)由有向或無向的連線連接

3、,而障礙物群中最短路徑指的是圖中兩點(diǎn)通過一條折線或曲線相連,不與任一障礙物發(fā)生碰撞,且這條折線或曲線的路徑長(zhǎng)度或者代價(jià)最小。3幾種經(jīng)典算法現(xiàn)有的算法分為兩類:走迷宮(Maze-running)算法和線搜索(Line-searching)算法。2障礙物群中最短路徑問題的定義最短路徑問題是VLSI設(shè)計(jì)和幾何信息系統(tǒng)中的基本問題,是一種計(jì)算機(jī)圖形搜索算法,即在出發(fā)點(diǎn)和目標(biāo)點(diǎn)之間找出總代價(jià)最低的路徑。路徑尋優(yōu)算法一方面要完成探索最低代價(jià)的路徑,另一方面要做到盡可能快,盡可能少占用內(nèi)存,即盡可能34Lee算法為第一個(gè)走迷宮算法,它是廣度優(yōu)先搜索法的一個(gè)應(yīng)用,迷宮算法基于單元格點(diǎn)搜索,在時(shí)間和空間上是低效

4、的,因此人們提出了線搜索算法。線搜索算法的基本思想是構(gòu)造一個(gè)代表障礙和結(jié)點(diǎn)位置的圖,通過在圖中尋找最短路徑得到原格點(diǎn)中的最短路徑1。此|TechniquesofAutomation&Applications計(jì)算機(jī)應(yīng)用自動(dòng)化技術(shù)與應(yīng)用2003年第22卷第1期類算法有以下特點(diǎn):(1)構(gòu)造的圖比原單元格點(diǎn)圖稀疏;(2)構(gòu)造的圖具有代表性,圖中的路徑與原網(wǎng)格中的路徑是寸靈活調(diào)整探索起點(diǎn)及探索方向。4改進(jìn)的線探索算法由于走迷宮法是基于網(wǎng)格的布線算法,采用這種算法要對(duì)實(shí)際布線圖作一定簡(jiǎn)化,以使得圖形坐標(biāo)數(shù)據(jù)位于網(wǎng)格上。且數(shù)據(jù)存儲(chǔ)空間和路徑搜索時(shí)間隨線間距離的減少以平方關(guān)系而增加,當(dāng)布線圖比較復(fù)雜,

5、元器件特別多時(shí),連接線寬度和線間距離越來越少,走迷宮算法就顯得有些力不從心了。本文主要對(duì)線探索算法進(jìn)行了改進(jìn),下面詳細(xì)敘述。等價(jià)的;(3)對(duì)源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn),構(gòu)造的圖中存在與原網(wǎng)格中的最短路徑對(duì)應(yīng)的路徑;(4)構(gòu)造圖的復(fù)雜度決定了算法的復(fù)雜度。311李氏迷宮算法的基本思想李氏迷宮算法首先將布線區(qū)域分成單位網(wǎng)格,然后沿著網(wǎng)格走線,且每個(gè)網(wǎng)格在一個(gè)方向上只允許布一條線,并在此基礎(chǔ)上搜索路徑。使用矩陣網(wǎng)格后,布線實(shí)際上是沿著曼哈坦路徑實(shí)現(xiàn)的。在布線算法中,由于通常意義上的兩點(diǎn)(x1,y1),(x2,y2)之間的歐幾里德距離sqrt(x1-x2)3(x1-x2)+(y1-y2)3(y1-y2)計(jì)算涉及

6、大量的浮點(diǎn)運(yùn)算,411幾個(gè)基本概念(1):,其某些區(qū)段是所():(x1,y1),(x2,y2dm=+x1-x2|+y1-Y2|,。是一條以當(dāng)前點(diǎn)為起點(diǎn),有預(yù)定終點(diǎn)和一定寬度的水平、垂直或斜向射線。探索線的寬度即用來連接待連點(diǎn)對(duì)的連線寬度。探索過程實(shí)質(zhì)上是一個(gè)檢查計(jì)算過程,就是按照從起點(diǎn)至預(yù)定終點(diǎn)的方向,逐一檢查前面或兩側(cè)是否有元器件或已布連線等障礙物阻礙探索線直通預(yù)定終點(diǎn)的過程2。(3)繞障偏移量:值得注意的是,采用這種算法之后,兩點(diǎn)間的最短路徑將不唯一。李氏算法就是在上述網(wǎng)格中實(shí)現(xiàn)的,它的基本思想可以描述為波的傳播過程的模擬。在一個(gè)存在障礙的湖面上,若需尋找連接A,B兩點(diǎn)的最小路徑,可以在A

7、點(diǎn)投下一枚石子,然后觀察所引起的水波傳播情況。假定“水波”傳播時(shí)能量無損失,當(dāng)遇到障礙時(shí),波產(chǎn)生反射,最先到達(dá)的目標(biāo)點(diǎn)波前所經(jīng)過的路徑必定是一條最短距離。而且只要兩點(diǎn)間有通路存在,則自A點(diǎn)擴(kuò)散出去的波一定能傳播到B點(diǎn)。為了繞過障礙,最短路徑不應(yīng)與圖元相交,由于臨界最短路徑可能經(jīng)過了障礙物的邊界,因此必須加上一定的偏移量,稱為繞障偏離量。相對(duì)每一障礙,可有正負(fù)兩個(gè)繞障偏移量。其中,負(fù)偏移量小于0,正偏移量大于0。(4)登陸點(diǎn)312線探索布線算法線探索布線算法本質(zhì)上是一種無網(wǎng)格布線算法,在線探索法中,不用存儲(chǔ)各網(wǎng)點(diǎn)信息,只須存儲(chǔ)外形尺寸,存儲(chǔ)各連接線寬度及端點(diǎn)坐標(biāo)。但在具體實(shí)現(xiàn)上,為了提高搜索效率

8、,往往外形尺寸一致、連線寬度一致,并將連線端點(diǎn)坐標(biāo)網(wǎng)格化,線探索是否依賴于網(wǎng)格,關(guān)鍵在于坐標(biāo)是否網(wǎng)格化。在基于網(wǎng)格的線探索中,探索線端點(diǎn)及回溯處理時(shí)的步長(zhǎng)都以網(wǎng)格為單位計(jì)算。在無網(wǎng)格線探索方案中,坐標(biāo)以最小設(shè)計(jì)精度為單位,探索線端點(diǎn)則根據(jù)障礙的幾何尺寸及探索線與障礙之間的允許最小間隙而計(jì)算,回溯處理以線間最小距離為步長(zhǎng),并結(jié)合障礙的幾何尺當(dāng)前點(diǎn)可見的障礙物上最近的頂點(diǎn)。(5)分離點(diǎn)繞過障礙物時(shí)探索線的起點(diǎn)。圖1示意圖如圖所示,當(dāng)運(yùn)動(dòng)物體M沿探索線a前進(jìn),如果碰到障礙TechniquesofAutomation&Applications|35自動(dòng)化技術(shù)與應(yīng)用2003年第22卷第1期計(jì)算機(jī)

9、應(yīng)用物O,則O的頂點(diǎn)必定分布在a的兩側(cè),且部分邊是M可見的(圖中的實(shí)線邊),部分是不可見的(虛線邊),把M可見的障礙得到臨界最短路徑S-v1-v2-v3-E2(圖中紅線),該路徑的某些區(qū)段是元器件的邊界。物的頂點(diǎn)分成兩組,矢量a左側(cè)的頂點(diǎn)歸入L組,右側(cè)的歸入R組。另設(shè)VL和VR分別是L和R組中離a最遠(yuǎn)的兩個(gè)頂點(diǎn)。如果VL比VR離a更遠(yuǎn),則令C=R,否則令C=L。VC就是登陸點(diǎn)。M繞過障礙物時(shí)首先向登陸點(diǎn)靠近。找到登陸點(diǎn)后,接著就是如何繞過障礙物O。先把S與登陸點(diǎn)VC連接,再把VC與E連接起來。視VC為當(dāng)前點(diǎn),記做P,如果PE不與障礙物相交,表明已繞過了障礙物,稱此P點(diǎn)為M繞過障礙物O的分離點(diǎn)。

10、否則把當(dāng)前點(diǎn)從P出發(fā)順著(當(dāng)P在SE的左側(cè))或逆著(當(dāng)P在SE的右側(cè))O的邊界移到下一個(gè)頂圖2兩點(diǎn)間的最短路徑下一步,S-v2-v-)。點(diǎn)上。繞過一個(gè)障礙物后,如果后面還有障礙物,就把當(dāng)前點(diǎn)作為新的起點(diǎn)重復(fù)上述過程,直到繞過所有障礙物到達(dá)終點(diǎn)E412基本思想(1),5結(jié)論筆者將本算法的思想應(yīng)用到電路布線圖的繪制和GIS道路搜索應(yīng)用中,都取得了較好的效果。由于本算法的探索線是從起點(diǎn)指向終點(diǎn)的射線,且求出的最短路徑是在臨界最短路徑的基礎(chǔ)上加上繞障偏移量得到的結(jié)果,繞障偏移量的計(jì)算也存在一定誤差,因此最終得到的兩點(diǎn)間繞過障礙物的最短路徑是近似最短路徑3。最短路徑。(2)以第一步求出的臨界最短路徑為基

11、準(zhǔn),考慮線寬等因素,加上繞障礙偏移量,得出最終的最短路徑,該路徑不與障礙物相交。413算法步驟首先將給定的起始點(diǎn)和中止點(diǎn)連起來,得到線段SE,從S指向E的射線SE為探索線,沿探索線探索前方是否有障礙物。找出與SE相交的第一個(gè)障礙物集合O,如果O不存在,則SE即為所求的解,否則在O上找到登陸點(diǎn),繞過O。如果O的分離點(diǎn)D不能直達(dá)中止點(diǎn)E,中間存在障礙物O,則求出以D為出發(fā)6參考文獻(xiàn)1周智,等1用O(tlogt)的連接圖求有障礙時(shí)的最短路徑J1計(jì)算機(jī)學(xué)報(bào),1999,5點(diǎn),E為目標(biāo)點(diǎn)時(shí)O上的登陸點(diǎn)VC。然后用與上述同樣的方法求出D到VC的通路和VC到E的通路。如圖所示,a,b,c,d表示障礙物。S與E1之間沒有障礙物,最短路徑為SE1;S與E2間存在障礙物,首先沿探索線SE2探索,發(fā)現(xiàn)前方有障礙物b,則繞過障礙物b,分離點(diǎn)為v1,然后以v1為新的起點(diǎn),連接v1,E2,得探索線v1E2,繼續(xù)沿v1