多边形地物绕行路径生成算法的设计与应用

1、多边形地物绕行路径生成算法的设计与应用关键词多边形;路径;生成绕行算法 作者简介庾露,广西师范学院硕士研究生,研究方向:地理信息系统编程与算法,广西南宁,530001 中图分类号 P283.7 文献标识码 A 文章编号 1007-7723(2010)02-0046-0003 一、引言 在现实世界中,人们常常会在行进过程中避开一些面状地物。例如,上下班途中需绕行一部分城镇建筑物,在野外行军过程中需绕开高大山岭、雷区、敌军控制区。怎样才能快速绕过障碍物并选择合理的行进方案,成为行进过程中首要考虑的问题。一般的解决思路是在行进区域内预先构建网格和节点,以此带入路径分析算法(如最短路径算法、最优路径算

2、法),最后生成行进路线结果。但是在面状要素地块繁多复杂,而且缺少现成道路网格的地图中,上述依靠网格和节点的方法不能快速地生成路径。本文针对上述不足,模拟现实行进中的一般规律,提出了仅依靠多边形作为障碍物、开始和结束点作为初始条件的多边形绕行算法,并通过实例证明了该算法的可行性。 二、生成算法的前提 前提1:本算法所处理的对象为给定二维区域内有限多个多边形,并且这些多边形有部分是离散的。 前提2:本算法生成的路径为自由空间中连接起点和终点的折线,折线的每一段均为直线段。 前提3:本算法视多边形为不可通过区域,多边形以外给定区域内的空间均视为可通过区域。 三、预处理 由于本算法依赖于对多边形的各端

3、点做计算,所以必须对给定区域内的多边形进行必要的预处理。预处理的目的是检查给定区域内多边形的拓扑关系以及自身的空间属性是否满足算法能正确运行的需要;如不满足则需要作适当的修改。 1.对给定区域内存在相交、相邻(即两个多边形共享一条边)关系的多边形,合并为一个多边形。 2.对给定区域内存在真包含(即多边形的每条边是否都在另一多边形内 )关系的多边形,删除其中被包含的多边形。 3.对给定区域内存在自相交(即多边形的部分边界存在相交关系)的多边形,确定交点,从交点位置将原多边形分割成若干个彼此相接接点为原交点的多边形,最后合并这些多边形。 4.对给定区域内存在内岛的多边形,删除内岛。 四、路径生成

4、步骤1:确定初始路径L。初始路径是由起点S和终点D组成的一条有向直线段。 步骤2:选定一个与L相交的多边形A。判断该L的有效范围内是否存在与多边形相交。如果不存在,则直接返回L并退出函数;如果存在,可以选定其中任意一个作为被绕行的目标多边形A加入余下的步骤进行运算(这里考虑到了L可能与多个多边形相交的情况。因为整个算法可以用一个返回值为折线,参数为线段和多边形的函数实现。所以,只需任取其中一个与L相交的多边形,剩余的多边形绕行路径可以在后续逐步生成的路径中做递归完成)。 步骤3:根据L的行进方向,分别生成均包含以最近交点c1为起点、最远交点c2为终点,A的左边界点集序列LB和右边界点集序列RB

5、。这里的最近交点c1和最远交点c2分别指的是,L与A相交形成的一系列交点中离S最近和最远的两个交点(如图1所示,其中LB=c1,a5,a6,a7,a8,a9,a10,a11,a0,a1,c2,RB=c1,a4,a3,a2,c2)。 步骤4:根据需要,确定绕行的边界(沿左侧还是右侧绕行),生成包含S、D以及绕行边界上所有节点a1、a2an的顺序数组nA。数组各元素排列顺序如下nA=S、a1、a2an、D(如图1所示,假设确定从左侧绕行nA=S、a5、a6、a7、a8、a9、a10、a11、a0、a1、D)。 步骤5:判断线段SD连线是否与A或其他多边形相交,若无相交则返回线段SD结束函数;若存在

6、则继续判断相交多边形是否为A,若存在其他多边形(记为A);则将线段SD和A加入递归,否则执行余下操作。 步骤6:从nA中的S出发依次与后续节点做临时线段tempL,只记录这些临时线段中最后与A相接(即tempL与A有且只有一个公共点,且该公共点是A的一个端点也是tempL的一个端点)的线段cL。若不存在tempL与A相接的情况,则cL是以S和 nA中S后一个元素为端点的线段,即cL与多边形边界叠置(如图2所示,假设从多边形左侧绕行)。 步骤7:判断cL是否与其他多边形相交(记为A),若存在相交则将cL和A加入递归;否则记录cL的终点为新的起点S,并根据新起点S在原nA的位置删除S之前的元素重建

7、nA(如图3所示重建后的nA=S,a0,a1,D),并重复步骤4、5、6直至最终结束函数。 五、相关应用 (一)生成最短路径 本算法可用于生成最短路径。由于本算法是逐步生成路径的,即使能确定绕行方向也不能预先计算行进过程中是否会与其他多边形相交。因此可以使用枚举思想,对于路径行进过程中相交的多边形均进行左右绕行,最终生成多个路径。比较并记录其中最短的路径,从而完成不基于网格数据,绕行多边形地物的最短路径生成。 (二)复杂多边形地物的路径生成对于存在回绕、嵌套、相交、相邻、岛区以及凹凸多边形混杂的区域,本算法模拟一般行进规律,能较快速并且合理地生成多条绕行路径,为物体在给定区域两点间的移动问题提

8、供参考(图4为该算法在迷宫问题上的应用)。 六、结论 本文从现实问题出发,模拟人们日常行进规律。通过研究行进路径与多边形边界的顶点以及多边形本身的拓扑关系,使用较为简单的方法,给出了对给定区域多个多边形地物的绕行算法的具体实现步骤。通过上文中的测试表明,该算法具有良好的适应性,能够在包含复杂多边形的环境下正确运行,得到预期的结果。但是在分析了算法的实现步骤上可以发现算法的时间和空间消耗与给定区域内多边形个数以及绕行多边形顶点数成正比。主要表现在渐进式寻找相接顶点生成路径阶段,不但要判断线段是否与被绕行多边形相交,还需判断最后记录的线段是否与其他多边形相交。由于判断线段与多边形相交的运算通常情况下使用浮点运算,从而增大了运算量。因此,可以考虑采用一些优化的算法,如对被绕行多边形再作分析,判别凹凸边形,从而再逐点寻找相接顶点阶段忽略部分端点以减少运算量,等等。 参考文献 1吴立新,史文中.地理信息系统原理与算法M.北京:科学出版社,2003. 2易辰,樊晓