【计算几何 十五章】可见性图：求最短路径

本文涉及知识点

数学 几何

预备知识

直线与线段的交点在射线的投影是连续函数。

假定直线和射线不平行。
假定射线起点是原点，弧度是α \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_0=0 \\ t\sin\alpha - k\times dy - y_0=0tcosα−k×dx−x0​=0tsinα−k×dy−y0​=0
根据克莱姆法则：D=− cos ⁡ α × d y + d x × sin ⁡ a -\cos\alpha\times dy+dx \times \sin a−cosα×dy+dx×sina，由于存在交点，则D ≠ 0 D\neq 0D=0
我们无需计算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为所有障碍物所包含的边数。

扩展阅读

测试环境

操作系统：win7 开发环境： VS2019C++17
或者 操作系统：win10 开发环境： VS2022C++17
如无特殊说明，本算法用**C++**实现。