问题历史/原点
最近我偶然发现Twitch.TV上的 Channels 来自执行经典游戏速度的玩家 . 其中一人打了The Legend of Zelda - A Link to the Past . 我看到了很多低效的动作，我开始怀疑 - 鉴于世界 Map 数据 - 是否有可能编写一个执行完美速度的机器人 . 一个经常出现的子问题是找到一个平面中两点之间的最短路径，我认为这是一个非常有趣的问题，我开始对此进行更多的研究 .
类似的Stackoverflow问题已经发布
Finding path obstacles in a 2D image
Algorithm to detect corners of paper sheet in photo
... 和更多
其中答案总是为Superproblem（如下所述）提供不同的解决方案，例如使用基于网格的方法，而不是我感兴趣的实际子问题（如下所述） .
Superproblem解决方案描述
给定平面中的两个点 X=(x1,x2) 和 Y=(y1,y2) - 如果平面包含路径可能无法通过的障碍物/区域，那么从 X 到 Y 的最短路径是多少？
Differently/ More visually 从Link的当前位置到 Map 上的第二个红点的最短路径是什么，因为他无法爬过墙壁或穿过灌木丛？
这个问题通常被称为Eucledian Shortest Path Problem，并且可以在Polynomial time中在二维情况下求解 . 真棒！
为此，构造了一个带有 V= {X,Y} U {"Corner-Points of obstacles}" 的所谓的Visibility Graph . 当且仅当可以从 P 到 Q 绘制直线而不穿过任何障碍物时，边缘插入点 P and Q 之间 . 每个边缘由它连接的点之间的Eucledian Distance加权 .
在上面的示例中，可见性图表看起来像这样 . 为了便于阅读，我省略了一些边缘和重量 . 阴影区域显示障碍 .
然后，可以使用可见性图上的开发者最喜欢的最短路径算法来计算最短路径 .
子问题描述
让我们首先将障碍定义为不可通过的地形的连续区域 . 如何找到所有障碍物的最小数量的所需角落（以及角落的坐标）来构建执行最短路径计算所需的最小可能性图表？
对于矩形障碍物，很容易找到角落，因为草图中只有很少的锋利边缘......
...或应用于游戏内场景
然而，一旦障碍物具有对角线“前线”，由于诱导的拼图模式（无论角度），获得角落变得非常重要 . 下面的屏幕截图说明了这个问题：左侧图像显示哪个坐标点应该被识别为角点，而右侧图片显示由于“竖锯” - 对角线图案而插入附加点的位置 .
现在的问题是：如何从可能非常大的可见性图中排除/防止这些不必要的角点（被插入）？
1 回答
如何查看每个点周围的点，如果您发现两个点完全相反但没有穿过“实心”，那么您就知道实际上有一个删除候选者 . 在删除之前对所有点执行此操作，然后一次性删除所有这些候选项 .
这将照顾水平，垂直和对角线 . 如果将半径扩展到两个或更多，则还可以检测其他角度的“线”上的冗余点 .
时间复杂度几乎是O（n）（当n是点数时），因为你将检查每个点周围的固定数量的点以找到移除候选者，例如：
Radius 1 - 4 adjacent point pairs to check per point:
=>检查对（1 8），（2 7），（3 6），（4 5）
Radius 2 - 8 adjacent point pairs to check per point:
=>检查对（1 G），（2 F），（3 E），（4 D），（5 C），（6 B），（7 A），（8 9）