Table of Contents:

下图的5个凸多边形是已经生成的导航网格，多边形外部的区域为不可行走区域，current为起点，goal为终点，从图中就可以看出最短路径为图中红线，蓝色圈出的点为我们需要找出的点。所有多边形顶点均按逆时针方向存储

（1）下图显示出各区域之间的入口，即多边形的临边。由图中可以看出每个临边均为起点穿出该多边形区域的边，故以下称该边为穿出边。

（2）首先找到起始点所在的多边形和穿出边的两个端点，由起点连接两个端点，形成两个线段lineLeft 和lineRight。如下图。绿色圈表示左点，红色表示右点（左点、右点是根据多边形顶点保存顺序而来）。

（3）继续找到下一个穿出边的两个端点，判断新的左点是否在lineLeft 和lineRigh之间，如果在，则更新lineLeft为起点到新左点的线段。

同样处理新穿出边的右点，如下图

该步最后得到两个新的线段，如下图。

（4） 继续判断下一个穿出边的两个端点，如下图，新的左点在lineLeft和lineRight的外面，则不更新线段。

下图说明新的右点在两条直线之间，更新lineRight。

该步最后得到两个新的线段，如下图。

（5） 继续循环判断下一个穿出边的两个端点，该穿出边的两个端点都在lineRight的右侧，表示lineRight的终点即为路径的一个拐角点。

（6） 循环以上步骤都可以找到从起点到终点的一条完整路径。

参考链接