本文涉及知识点

数学 几何

预备知识

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

假定直线和射线不平行。
假定射线起点是原点，弧度是$\alpha$，直线是：$P:=(x_0,y_0)+kv$。
令交点距离原点t， k和t $\alpha$是未知量，其它是已知量。则：
$$\begin{gathered} t\cos \alpha -k\times dx-x_0=0 \\ t\sin \alpha -k\times dy-y_0=0 \end{gathered}$$
根据克莱姆法则：D=$-\cos \alpha \times dy+dx\times \sin a$，由于存在交点，则$D\ne 0$
我们无需计算$D_1$，因为D_1是连续函数。
故$\frac{D_1}{D}$是连续函数。

前言

本章讨论的问题仅仅是：如何为沿平面运动的机器人规划出一条欧式最短路径。

1 点机器人的最短路径

倘若障碍物是闭集，那么最短路径不存在，对于任意一条路径，我们都可以将它超某个障碍物靠拢，从而得到一条更短的路径。

多边形路径中内部顶点(inner vertext)- 即该路径上除起点、终点之外的任何顶点。

15.11：穿行于一组互不相交的多边形障碍物S之间、从$p_{start}通往p_{goal}$的任何一条最短路径T，都是一条多边形路径，其中所有的内部顶点都是S的顶点。
T一定都是线段，令T在p处是弧线，则存在以p中心的圆和所有的障碍物相切或相邻。T一定和圆相交于两点，连接这两点距离更短。

同理，T内部顶点一定是S的顶点，否则用和圆相交的两点构成的线段替换。
根据上述特性，可构造线路图，并借助它找到最短路径。这张线路图，成为S的可见图，记作$G_{vis}(S)$。其中每个节点对应于S中的顶点；若顶点v和w可以相互看见，则在它们对应的节点之间引入一条弧。可见指的是线段$\overline{vw}不与S中的任意障碍物相交。$障碍物任何一条边的两个端点，总是相互可见的。T除了第一条边和最后一条边外都是可见边，为了让这两条边成为可见边，我们将起点、终点也加到S中。
推理15.2：穿行于一组互不相交的多边形障碍物S之间、从$p_{start}通往p_{goal}$的任何一条最短路径，必然是由可见性图$G_{vis}(S^{\ast })$中的若干条弧连接而成的，其中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_{start}通往p_{goal}$的任何一条最短路径，都可以在O(nnlogn)的时间内构造出来，其中n为各障碍物所含边的总数目。

2 构造可见性图

定理15.4：任意给定一组互不相交的多边形障碍物S，其可见性图可以在O(nnlogn)时间内构造出来，其中n为s的总边数。

旋转扫描线法

$扫描线（摄像）以e_1为中心，从\alpha 旋转到\beta ，$如果没有新的线段与射线相交，也没有线段不再和射线相交，则各线段的交点次序不会发生变化。
忽略和射线平行的线段。线段和射线的交点在射线的投影是连续函数，两个连续函数的差仍然是连续函数。根据介值定理，连续函数的值不会从正数越过0，跳跃到负数。
set要自定义比较函数，且比较函数与射线角度$\alpha$相关。

3 平移运动多边形机器人的最短路径

先计算出-R(即R的对称镜像)与每个障碍物的闵可夫斯基和，然后再记下所得出的C-空间障碍物的并集。于是问题就转换成点机器人。
定理15.5：设机器人R的形状是凸的，其复杂度为常数，可以在一组多边形障碍物之间做平移式运动。对于任何给定的起始和目标位置，我们都能够在O(nnlogn)的时间内，为R规划出一条不发生碰撞的最短路径。其中n为所有障碍物所包含的边数。

扩展阅读

计算几何为骨，排样优化为魂
作品：亲士CAD工具箱
经典文章推荐：二维排样
万物皆数学
查阅鄙人的博文，请点击博文下载学院导航
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。

测试环境

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