矢量图中绕过障碍物的最短路径算法研究

1、自动化技术与应用2003年第22卷第1期计算机应用矢量图中绕过障碍物的最短路径算法研究AlgorithmsForTheShortestPathRoundingObstaclesInVectorGraphics华中科技大学陈传波唐浩ChenChuanbo,TangHao摘要:通过比较几种常见的有障碍物时求最短路径的算法,径的近似算法。关键词:最短路径探索线绕障偏移量Abstract:ThispapercomparesseveralpathontheLine-searchingalgorithm,bringsforwardanim2provedalgorithmKewords:TheOffsetf

2、orobstaclerounding中图分类号:TP11:A文章编号:100327241(2003)01200342031引言运输管理以及工程设计的许多方面,如各种工艺路线的安排,电网及管道线网的铺设,电子地图的寻路等问题,都与图的最短路径问题密切相关。在某些工程应用中,如设计电路图或布线图时,常常碰到这样的情况:电路元件和已布好的连接线成为了布线障碍。为了避免新的连接线穿越元器件,就必须按一定的策略使得某些已作好的连接线作出规避,同时求出障碍群中两点间的最短路径,按这条路径为新作的连接线布线。降低算法的时间复杂度和空间复杂度。通常求最短路径是在一个连通图中进行,各个节点由有向或无向的连线连接

3、,而障碍物群中最短路径指的是图中两点通过一条折线或曲线相连,不与任一障碍物发生碰撞,且这条折线或曲线的路径长度或者代价最小。3几种经典算法现有的算法分为两类:走迷宫(Maze-running)算法和线搜索(Line-searching)算法。2障碍物群中最短路径问题的定义最短路径问题是VLSI设计和几何信息系统中的基本问题,是一种计算机图形搜索算法,即在出发点和目标点之间找出总代价最低的路径。路径寻优算法一方面要完成探索最低代价的路径,另一方面要做到尽可能快,尽可能少占用内存,即尽可能34Lee算法为第一个走迷宫算法,它是广度优先搜索法的一个应用,迷宫算法基于单元格点搜索,在时间和空间上是低效

4、的,因此人们提出了线搜索算法。线搜索算法的基本思想是构造一个代表障碍和结点位置的图,通过在图中寻找最短路径得到原格点中的最短路径1。此|TechniquesofAutomation&Applications计算机应用自动化技术与应用2003年第22卷第1期类算法有以下特点:(1)构造的图比原单元格点图稀疏;(2)构造的图具有代表性,图中的路径与原网格中的路径是寸灵活调整探索起点及探索方向。4改进的线探索算法由于走迷宫法是基于网格的布线算法,采用这种算法要对实际布线图作一定简化,以使得图形坐标数据位于网格上。且数据存储空间和路径搜索时间随线间距离的减少以平方关系而增加,当布线图比较复杂,

5、元器件特别多时,连接线宽度和线间距离越来越少,走迷宫算法就显得有些力不从心了。本文主要对线探索算法进行了改进,下面详细叙述。等价的;(3)对源结点和目标结点,构造的图中存在与原网格中的最短路径对应的路径;(4)构造图的复杂度决定了算法的复杂度。311李氏迷宫算法的基本思想李氏迷宫算法首先将布线区域分成单位网格,然后沿着网格走线,且每个网格在一个方向上只允许布一条线,并在此基础上搜索路径。使用矩阵网格后,布线实际上是沿着曼哈坦路径实现的。在布线算法中,由于通常意义上的两点(x1,y1),(x2,y2)之间的欧几里德距离sqrt(x1-x2)3(x1-x2)+(y1-y2)3(y1-y2)计算涉及

6、大量的浮点运算,411几个基本概念(1):,其某些区段是所():(x1,y1),(x2,y2dm=+x1-x2|+y1-Y2|,。是一条以当前点为起点,有预定终点和一定宽度的水平、垂直或斜向射线。探索线的宽度即用来连接待连点对的连线宽度。探索过程实质上是一个检查计算过程,就是按照从起点至预定终点的方向,逐一检查前面或两侧是否有元器件或已布连线等障碍物阻碍探索线直通预定终点的过程2。(3)绕障偏移量:值得注意的是,采用这种算法之后,两点间的最短路径将不唯一。李氏算法就是在上述网格中实现的,它的基本思想可以描述为波的传播过程的模拟。在一个存在障碍的湖面上,若需寻找连接A,B两点的最小路径,可以在A

7、点投下一枚石子,然后观察所引起的水波传播情况。假定“水波”传播时能量无损失,当遇到障碍时,波产生反射,最先到达的目标点波前所经过的路径必定是一条最短距离。而且只要两点间有通路存在,则自A点扩散出去的波一定能传播到B点。为了绕过障碍,最短路径不应与图元相交,由于临界最短路径可能经过了障碍物的边界,因此必须加上一定的偏移量,称为绕障偏离量。相对每一障碍,可有正负两个绕障偏移量。其中,负偏移量小于0,正偏移量大于0。(4)登陆点312线探索布线算法线探索布线算法本质上是一种无网格布线算法,在线探索法中,不用存储各网点信息,只须存储外形尺寸,存储各连接线宽度及端点坐标。但在具体实现上,为了提高搜索效率

8、,往往外形尺寸一致、连线宽度一致,并将连线端点坐标网格化,线探索是否依赖于网格,关键在于坐标是否网格化。在基于网格的线探索中,探索线端点及回溯处理时的步长都以网格为单位计算。在无网格线探索方案中,坐标以最小设计精度为单位,探索线端点则根据障碍的几何尺寸及探索线与障碍之间的允许最小间隙而计算,回溯处理以线间最小距离为步长,并结合障碍的几何尺当前点可见的障碍物上最近的顶点。(5)分离点绕过障碍物时探索线的起点。图1示意图如图所示,当运动物体M沿探索线a前进,如果碰到障碍TechniquesofAutomation&Applications|35自动化技术与应用2003年第22卷第1期计算机

9、应用物O,则O的顶点必定分布在a的两侧,且部分边是M可见的(图中的实线边),部分是不可见的(虚线边),把M可见的障碍得到临界最短路径S-v1-v2-v3-E2(图中红线),该路径的某些区段是元器件的边界。物的顶点分成两组,矢量a左侧的顶点归入L组,右侧的归入R组。另设VL和VR分别是L和R组中离a最远的两个顶点。如果VL比VR离a更远,则令C=R,否则令C=L。VC就是登陆点。M绕过障碍物时首先向登陆点靠近。找到登陆点后,接着就是如何绕过障碍物O。先把S与登陆点VC连接,再把VC与E连接起来。视VC为当前点,记做P,如果PE不与障碍物相交,表明已绕过了障碍物,称此P点为M绕过障碍物O的分离点。

10、否则把当前点从P出发顺着(当P在SE的左侧)或逆着(当P在SE的右侧)O的边界移到下一个顶图2两点间的最短路径下一步,S-v2-v-)。点上。绕过一个障碍物后,如果后面还有障碍物,就把当前点作为新的起点重复上述过程,直到绕过所有障碍物到达终点E412基本思想(1),5结论笔者将本算法的思想应用到电路布线图的绘制和GIS道路搜索应用中,都取得了较好的效果。由于本算法的探索线是从起点指向终点的射线,且求出的最短路径是在临界最短路径的基础上加上绕障偏移量得到的结果,绕障偏移量的计算也存在一定误差,因此最终得到的两点间绕过障碍物的最短路径是近似最短路径3。最短路径。(2)以第一步求出的临界最短路径为基

11、准,考虑线宽等因素,加上绕障碍偏移量,得出最终的最短路径,该路径不与障碍物相交。413算法步骤首先将给定的起始点和中止点连起来,得到线段SE,从S指向E的射线SE为探索线,沿探索线探索前方是否有障碍物。找出与SE相交的第一个障碍物集合O,如果O不存在,则SE即为所求的解,否则在O上找到登陆点,绕过O。如果O的分离点D不能直达中止点E,中间存在障碍物O,则求出以D为出发6参考文献1周智,等1用O(tlogt)的连接图求有障碍时的最短路径J1计算机学报,1999,5点,E为目标点时O上的登陆点VC。然后用与上述同样的方法求出D到VC的通路和VC到E的通路。如图所示,a,b,c,d表示障碍物。S与E1之间没有障碍物,最短路径为SE1;S与E2间存在障碍物,首先沿探索线SE2探索,发现前方有障碍物b,则绕过障碍物b,分离点为v1,然后以v1为新的起点,连接v1,E2,得探索线v1E2,继续沿v1