平面中多边形障碍下最短路径的求解.pdfVIP

平面中多边形障碍下最短路径的求解.pdf

  1. 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
  2. 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  3. 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  4. 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  5. 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  6. 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  7. 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
平面中多边形障碍下最短路径的求解

平面中多边形障碍下最短路径的求解 应用背景 最短路径求解是图论中最常见的问题之一。计算几何中这个问题主要起源于机器人运动 规划的问题。在一个平面中,考虑一个机器人从起始位置s,无碰撞地移动到目标位置t。 假定机器人只有两种运动——直线移动和原地转向,一个常见的目标就是规划一条路径,使 得机器人移动距离最短。 左图是一间办公室布局图;右图是其平面图,蓝线显示了Room13 移动到 Room8 的一条最短路径。10 问题定义 给定平面上一个起始点s 和一个目标点g ,以及若干多边形障碍物P , P , P … P ,然后 1 2 3 k 在平面上找到一条从s 到g 的多边形路径,其距离最短。我们这里限定多边形障碍物都为简 单多边形。由于此问题下,非简单多边形可以通过简单的切割合并操作转化为简单多边形, 所以我们后面遵循此限定。如下图所示: 该问题的一个常见思路是构造可见性图,然后对可见性图应用最短路径算法。可见性图 3 2 构造采用旋转式平面扫描算法 ,该算法实现上比较简单,复杂度为O(N logN)。在扫描算法 上进行改进4 ,可将复杂度降至O(NlogN+E) 。其中N 是顶点数,E 是可见性图的边数。在生 成可见性图后,可直接应用Dijkstra 最短路径算法,复杂度为O(NlogN+E) 。因此,在这种思 路下,算法的最优复杂度即为O(NlogN+E) 。 下图所示为该算法的一个图示。从图中可以看到,虽然构造出了可见性图,但是其中的 绝大部分线段并不出现在最短路径中,而且在Dijkstra 算法中也不一定用到。这是一个局限 性。 从实心红圈标注的一个门到建筑物内其他所有门的最短路径,用蓝线表示。细灰线表示的是可见性图, 用于构造最短路径。10 另一种思路是直观形象的波浪线算法,又称为continuous Dijkstra 算法,由J.S.B.Mitchell 首先提出5 6 ,后由Hershberger 和Suri 改进 ,复杂度降至理想的O(NlogN),这是目前理论最 优的算法。虽然本算法在理解上非常简单形象,但是实现上比较复杂,我们将在最后的部分 进行介绍。 图形界面 初始界面(左上角的红点为起点,右下角的蓝点为终点) :加入预定义的多边形,在下拉菜单 中有三角形、四边 形、五边形可选。 :加入自定义的多边形,每次左键生成一个顶点,最后右键生成多边形。 :删除多边形。左键点击多边形即可删除。 :清除所有多边形。 :移动多边形。左键可拖动多边形至任意自由区域。 :移动顶点。左键可拖动多边形顶点,任意改变多边形的形状;也可以拖 动起点和终点。 :运行测试样例。在下拉菜单 中有5 个测试样例,用于系 统的各项测试。 :保存。可以保存当前的样例至文件,以供下次重新运行。 我们为紫荆宿舍区画了一个简图,用于实验的简单测试说明: 首先使用画出各栋建筑的形状,其中大部分建筑如紫荆 3 号楼、桃李园等均可使用 直接生成,少数如 W 楼、C 楼等则需使用 构造;然后使用 将各建筑移动至正确位置,还可使用 对顶点进行移动,以精确描 绘建筑物形状。 在给定多边形障碍后,可以使用

文档评论(0)

***** + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

版权声明书
用户编号:8010045112000002

1亿VIP精品文档

相关文档