作 者：胡海星
版权说明
[1] 此文章原刊载于2001年《程序员》— 第11期 — 编程擂台。
[2] 该文版权所有，未经《程序员》编辑部允许不得任意转载或摘编。
[3] 我们转载此文，已征得《程序员》编辑部及作者的允许。
1、问题描述
在RPG游戏中，经常要设计精灵的移动路线。例如，地图上有若干障碍物，游戏精灵在坐标（X0, Y0）。游戏玩家希望用鼠标点击了地图上坐标（X1, Y1），电脑应该自动控制游戏精灵走到点（X1, Y1）。玩家希望精灵能尽快的移动到目标点，所以电脑应该计算出发点（X0, Y0）绕过所有的障碍物到达点（X1, Y1）的最短路线。
现在我们将问题简化一下。在地图上有n个障碍物，这些障碍物都是水平或竖直放置的矩形，他们的左上角和右上角坐标已知，矩形障碍物之间可能重叠。游戏精灵看作一个半径为r的圆，其圆心坐标（X0, Y0）已知。现在要让精灵移动到点（X1, Y1），即让它的圆心和点（X1, Y1）重合。请编程计算出最短路径长度。
1.1、输入
输入文件名：rpg.in
第一行是6个整数：n、X0、Y0、r、X1, Y1，后面的n行每行有四个整数a、b、c、d，分别代表一个矩形障碍物的左上角X坐标，左上角Y坐标，右下角X坐标，右下角Y坐标。
1.2、输出
输出文件名：rpg.out
输出最短路径长度，精确到小数点后两位。
数据规模限制：
0 <= n <= 5000， 坐标点范围在[ -100000，100000 ]之间。
程序可执行文件名：rpg.exe
2、问题分析
这个问题是一个有着广泛的实际应用背景的问题，该问题来源于机器人学领域，在计算几何学中称为算法的运动规划问题。
为了解决问题，我们先考虑问题的一种的简单情形：障碍物是已知的若干矩形，但是要移动的精灵是一个点P，要将该点P从S移动到T，找出最短路径。可以看出，从S到T的最短路径应该是一条由线段组成的折线，如图1所示。折线的两端点或者是S，T，或者是障碍物的顶点。因此我们可以把出发点S和目标点T以及所有矩形的顶点看成无向图的顶点，如果从某个点可以“看到”另一个点，则在这两个顶点之间连一条边，边的长度就等于两个点的距离。然后采用单源最短路径的Dijkstra算法求解。
 |
| 图1 |
下面考虑我们的这个问题。本题要移动的是一个圆，它和点不同之处在于圆心与障碍物之间的距离不可能超过圆半径r，否则就会出现重合现象。我们因此可以把圆收缩成一个点，把所有障碍物边界向外扩展r，这样就本题就转化成为同样是求点到点之间的最短路径问题了。
每个障碍物扩展后的边界就相当于把圆环绕该矩形移动一周后圆心所留下的轨迹，如图2所示。
 |
| 图2 |
我们把任何一条出发点到目标点的路径看成一根线，那么对应于最短路径的这根线显然应该是“绷紧”的，如图3所示。“绷紧”的线有什么特点呢？
- 由于障碍物不存在“角”，所以这根线应该可以分解为圆弧和线段，且两者交替出现。
- 所有的圆弧都是紧贴障碍物的边。
- 任何一条线段必然与它两端的两个圆弧相切（见图3）
 |
| 图3 |
由上述分析，我们有了这样一个想法：先求出所有的切线，包括出发点和目标点到所有圆弧的切线以及所有圆弧与圆弧之间的公切线，然后把这些切线看成是图中的顶点，给这些顶点赋一个等于切线长度的权值。如果某两条切线的两个顶点连一条边，边上的权值等于两个切点之间的劣弧长度。最后给这张地图加上一个源点和一个终点。在所有代表出发点到其他圆弧的切线的顶点与源点之间连一条边，边上的权值为0；同样地，在所有代表目标点到其他圆弧的切线的顶点与终点之间连一条边，边上的权值为0。这样，本题就转化为求源点到终点的最短路径问题了，这里的最短路径指的是经过所有顶点和边的权值之和最小。可用经典的Dijkstra算法求最短路径。
 |
| 图4 |
由于我们求切线的过程中有可能碰到切点处于障碍物内部的情况，因此要判断每条切线段是否合法。首先检验线段的两个端点是否处于障碍物内部；其次检验该线段是否与原来正方形的顶点，到线段的距离是否小于R；三者中有一者成立就可判定该切线段不合法。
另外还有如图4所示的一种特殊情况。在图4中，两个大小相同的障碍物在同一竖直位置上。它们有2条内公切线，8条外公切线，但是其中有6条外公切线是重复的。因此我们作如下规定：如果一条切线与某段圆弧相切且切点不在端点上，则该线段为不合法线段，应删去。
下面估计一下这个算法的时间复杂度。假设有n个矩形障碍物，则圆弧之间的公切线有4?Cn2O(n2)条，也就是说图的顶点数为O(n2)；求最短路径的时间复杂度为O(V2)，其中V为顶点数目；整个算法的复杂度为O(n4)。
算法的实现细节，包括求点到圆的切线、圆与圆的公切线、点到线段距离、圆弧上两点间距离等，请读者自行参考解析几何的相关资料。
到此这个问题已经全部解决。这个问题在图论建模和算法实现上提出了较高要求，尤其是算法实现部分特别繁琐。这需要我们在编程时不急不躁，仔细地考虑每个环节，这同时也是对我们算法实现的基本功的考验。
你好！跪求这篇文章的原文，里面图都看不到了，急求这篇文章图，恳请楼主发到邮箱1031741699@qq.com或者有网址链接，，不胜感激！