本文涉及知识点数学 几何预备知识直线与线段的交点在射线的投影是连续函数。假定直线和射线不平行。假定射线起点是原点弧度是α \alphaα直线是P : ( x 0 , y 0 ) k v P: (x_0,y_0)kvP:(x0,y0)kv。令交点距离原点t k和tα \alphaα是未知量其它是已知量。则t cos α − k × d x − x 0 0 t sin α − k × d y − y 0 0 t\cos\alpha- k\times dx-x_00 \\ t\sin\alpha - k\times dy - y_00tcosα−k×dx−x00tsinα−k×dy−y00根据克莱姆法则D− cos α × d y d x × sin a -\cos\alpha\times dydx \times \sin a−cosα×dydx×sina由于存在交点则D ≠ 0 D\neq 0D0我们无需计算D 1 D_1D1因为D_1是连续函数。故D 1 D \frac {D_1} DDD1是连续函数。前言本章讨论的问题仅仅是如何为沿平面运动的机器人规划出一条欧式最短路径。1 点机器人的最短路径倘若障碍物是闭集那么最短路径不存在对于任意一条路径我们都可以将它超某个障碍物靠拢从而得到一条更短的路径。多边形路径中内部顶点(inner vertext)- 即该路径上除起点、终点之外的任何顶点。15.11穿行于一组互不相交的多边形障碍物S之间、从p s t a r t 通往 p g o a l p_{start}通往p_{goal}pstart通往pgoal的任何一条最短路径T都是一条多边形路径其中所有的内部顶点都是S的顶点。T一定都是线段令T在p处是弧线则存在以p中心的圆和所有的障碍物相切或相邻。T一定和圆相交于两点连接这两点距离更短。同理T内部顶点一定是S的顶点否则用和圆相交的两点构成的线段替换。根据上述特性可构造线路图并借助它找到最短路径。这张线路图成为S的可见图记作G v i s ( S ) G_{vis}(S)Gvis(S)。其中每个节点对应于S中的顶点若顶点v和w可以相互看见则在它们对应的节点之间引入一条弧。可见指的是线段v w ‾ 不与 S 中的任意障碍物相交。 \overline{vw}不与S中的任意障碍物相交。vw不与S中的任意障碍物相交。障碍物任何一条边的两个端点总是相互可见的。T除了第一条边和最后一条边外都是可见边为了让这两条边成为可见边我们将起点、终点也加到S中。推理15.2穿行于一组互不相交的多边形障碍物S之间、从p s t a r t 通往 p g o a l p_{start}通往p_{goal}pstart通往pgoal的任何一条最短路径必然是由可见性图G v i s ( S ∗ ) G_{vis}(S^*)Gvis(S∗)中的若干条弧连接而成的其中S*:S ∪ { p s t a r t , p g o a l } S \cup \{p_{start},p_{goal}\}S∪{pstart,pgoal}。定理15.3穿行于一组互不相交的多边形障碍物之间、从p s t a r t 通往 p g o a l p_{start}通往p_{goal}pstart通往pgoal的任何一条最短路径都可以在O(nnlogn)的时间内构造出来其中n为各障碍物所含边的总数目。2 构造可见性图定理15.4任意给定一组互不相交的多边形障碍物S其可见性图可以在O(nnlogn)时间内构造出来其中n为s的总边数。旋转扫描线法扫描线摄像以 e 1 为中心从 α 旋转到 β 扫描线摄像以e_1为中心从\alpha旋转到\beta扫描线摄像以e1为中心从α旋转到β如果没有新的线段与射线相交也没有线段不再和射线相交则各线段的交点次序不会发生变化。忽略和射线平行的线段。线段和射线的交点在射线的投影是连续函数两个连续函数的差仍然是连续函数。根据介值定理连续函数的值不会从正数越过0跳跃到负数。set要自定义比较函数且比较函数与射线角度α \alphaα相关。3 平移运动多边形机器人的最短路径先计算出-R(即R的对称镜像)与每个障碍物的闵可夫斯基和然后再记下所得出的C-空间障碍物的并集。于是问题就转换成点机器人。定理15.5设机器人R的形状是凸的其复杂度为常数可以在一组多边形障碍物之间做平移式运动。对于任何给定的起始和目标位置我们都能够在O(nnlogn)的时间内为R规划出一条不发生碰撞的最短路径。其中n为所有障碍物所包含的边数。扩展阅读计算几何为骨排样优化为魂作品亲士CAD工具箱经典文章推荐二维排样万物皆数学查阅鄙人的博文请点击博文下载学院导航活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。 【计算几何 十五章】可见性图：求最短路径
本文涉及知识点数学 几何预备知识直线与线段的交点在射线的投影是连续函数。假定直线和射线不平行。假定射线起点是原点弧度是α \alphaα直线是P : ( x 0 , y 0 ) k v P: (x_0,y_0)kvP:(x0,y0)kv。令交点距离原点t k和tα \alphaα是未知量其它是已知量。则t cos α − k × d x − x 0 0 t sin α − k × d y − y 0 0 t\cos\alpha- k\times dx-x_00 \\ t\sin\alpha - k\times dy - y_00tcosα−k×dx−x00tsinα−k×dy−y00根据克莱姆法则D− cos α × d y d x × sin a -\cos\alpha\times dydx \times \sin a−cosα×dydx×sina由于存在交点则D ≠ 0 D\neq 0D0我们无需计算D 1 D_1D1因为D_1是连续函数。故D 1 D \frac {D_1} DDD1是连续函数。前言本章讨论的问题仅仅是如何为沿平面运动的机器人规划出一条欧式最短路径。1 点机器人的最短路径倘若障碍物是闭集那么最短路径不存在对于任意一条路径我们都可以将它超某个障碍物靠拢从而得到一条更短的路径。多边形路径中内部顶点(inner vertext)- 即该路径上除起点、终点之外的任何顶点。15.11穿行于一组互不相交的多边形障碍物S之间、从p s t a r t 通往 p g o a l p_{start}通往p_{goal}pstart通往pgoal的任何一条最短路径T都是一条多边形路径其中所有的内部顶点都是S的顶点。T一定都是线段令T在p处是弧线则存在以p中心的圆和所有的障碍物相切或相邻。T一定和圆相交于两点连接这两点距离更短。同理T内部顶点一定是S的顶点否则用和圆相交的两点构成的线段替换。根据上述特性可构造线路图并借助它找到最短路径。这张线路图成为S的可见图记作G v i s ( S ) G_{vis}(S)Gvis(S)。其中每个节点对应于S中的顶点若顶点v和w可以相互看见则在它们对应的节点之间引入一条弧。可见指的是线段v w ‾ 不与 S 中的任意障碍物相交。 \overline{vw}不与S中的任意障碍物相交。vw不与S中的任意障碍物相交。障碍物任何一条边的两个端点总是相互可见的。T除了第一条边和最后一条边外都是可见边为了让这两条边成为可见边我们将起点、终点也加到S中。推理15.2穿行于一组互不相交的多边形障碍物S之间、从p s t a r t 通往 p g o a l p_{start}通往p_{goal}pstart通往pgoal的任何一条最短路径必然是由可见性图G v i s ( S ∗ ) G_{vis}(S^*)Gvis(S∗)中的若干条弧连接而成的其中S*:S ∪ { p s t a r t , p g o a l } S \cup \{p_{start},p_{goal}\}S∪{pstart,pgoal}。定理15.3穿行于一组互不相交的多边形障碍物之间、从p s t a r t 通往 p g o a l p_{start}通往p_{goal}pstart通往pgoal的任何一条最短路径都可以在O(nnlogn)的时间内构造出来其中n为各障碍物所含边的总数目。2 构造可见性图定理15.4任意给定一组互不相交的多边形障碍物S其可见性图可以在O(nnlogn)时间内构造出来其中n为s的总边数。旋转扫描线法扫描线摄像以 e 1 为中心从 α 旋转到 β 扫描线摄像以e_1为中心从\alpha旋转到\beta扫描线摄像以e1为中心从α旋转到β如果没有新的线段与射线相交也没有线段不再和射线相交则各线段的交点次序不会发生变化。忽略和射线平行的线段。线段和射线的交点在射线的投影是连续函数两个连续函数的差仍然是连续函数。根据介值定理连续函数的值不会从正数越过0跳跃到负数。set要自定义比较函数且比较函数与射线角度α \alphaα相关。3 平移运动多边形机器人的最短路径先计算出-R(即R的对称镜像)与每个障碍物的闵可夫斯基和然后再记下所得出的C-空间障碍物的并集。于是问题就转换成点机器人。定理15.5设机器人R的形状是凸的其复杂度为常数可以在一组多边形障碍物之间做平移式运动。对于任何给定的起始和目标位置我们都能够在O(nnlogn)的时间内为R规划出一条不发生碰撞的最短路径。其中n为所有障碍物所包含的边数。扩展阅读计算几何为骨排样优化为魂作品亲士CAD工具箱经典文章推荐二维排样万物皆数学查阅鄙人的博文请点击博文下载学院导航活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。