(Euclidean Shortest Path) 检测平面内障碍物的角点
(Eucledian Shortest Path) Detecting corners of obstacles in plane
问题历史/起源
最近我在 Twitch.TV 上偶然发现了执行经典游戏速通的玩家的频道。其中一位演奏了 The Legend of Zelda - A Link to the Past。我看到了许多低效的动作，我开始怀疑——如果有世界地图数据——是否有可能编写一个执行完美速通的机器人。一个经常出现的子问题是找到平面中两点之间的最短路径，我认为这是一个非常有趣的问题，因此我开始对此进行更多研究。
已发布类似的 Whosebug 问题
Finding path obstacles in a 2D image
Algorithm to detect corners of paper sheet in photo
...以及更多
其中的答案总是为超级问题（如下所述）提供不同的解决方案，例如使用基于网格的方法，而不是我感兴趣的实际子问题（如下所述）。
超级问题解决方案说明
给定平面上的两个点 X=(x1,x2) 和 Y=(y1,y2) - 如果平面包含障碍物/区域，从 X 到 Y 的最短路径是什么路径不能引导？
不同/更直观假设他不能翻墙或走路，从Link的当前位置到地图上第二个红点的最短路径是什么穿过灌木丛？
这个问题通常被称为二维情况下的Eucledian Shortest Path Problem and can be solved in Polynomial time。太棒了！
为了实现这一点，在它连接的点之间有一个所谓的 Visibility Graph with V= {X,Y} U {"Corner-Points of obstacles}" is constructed. Edges are inserted between points P and Q if and only if it is possible to draw a straight line from P to Q without crossing any obstacle. Each edge is weighted by the Eucledian Distance。
在上面的示例中，可见性图表看起来像这样。为了便于阅读，我省略了一些边和权重。阴影区域表示障碍。
然后可以在可见性图上使用开发人员最喜欢的最短路径算法计算最短路径。
子问题描述
让我们首先将障碍物定义为不可通行地形的连续区域。如何找到所有障碍物所需角点的最少数量（以及角点的坐标）以构建执行最短路径计算所需的最小可能可见性图？
对于矩形障碍物，很容易找到拐角，因为只有少数锐边，如图所示...
...或应用于游戏场景
然而，一旦障碍物具有对角线“正面”，由于诱导的拼图图案（无论角度如何），获得角点变得非常重要。下面的截图说明了这个问题：左手边的图片显示了哪些坐标点应该被识别为角，而右手边的图片显示了由于对角线的“拼图”模式，额外的点将被插入的位置。
现在的问题是：如何排除/防止这些不必要的角点（插入到）可能非常大的可见性图中？
看看每个点周围的点怎么样，如果你发现两个点完全相反但不交叉 "solid" 那么你就知道你实际上有一个移除候选者。在删除任何点之前对所有点执行此操作，然后一次性删除所有这些候选点。
这将处理水平、垂直和对角线。如果将半径扩展到两个或更多，您还可以检测到其他角度 "lines" 上的冗余点。
时间复杂度几乎是 O(n)（当 n 是点数时），因为您将检查每个点周围固定数量的点以找到移除候选者，例如：
每个点要检查的半径 1 - 4 个相邻点对：
123
4X5
678
=> 检查对 (1 8), (2 7), (3 6), (4 5)
半径 2 - 每个点要检查的 8 个相邻点对：
1 2
34567
8X9
ABCDE
F G
=> 检查对 (1 G), (2 F), (3 E), (4 D), (5 C), (6 B), (7 A), ( 8 9)
问题历史/起源
最近我在 Twitch.TV 上偶然发现了执行经典游戏速通的玩家的频道。其中一位演奏了 The Legend of Zelda - A Link to the Past。我看到了许多低效的动作，我开始怀疑——如果有世界地图数据——是否有可能编写一个执行完美速通的机器人。一个经常出现的子问题是找到平面中两点之间的最短路径，我认为这是一个非常有趣的问题，因此我开始对此进行更多研究。
已发布类似的 Whosebug 问题
Finding path obstacles in a 2D image
Algorithm to detect corners of paper sheet in photo
...以及更多
其中的答案总是为超级问题（如下所述）提供不同的解决方案，例如使用基于网格的方法，而不是我感兴趣的实际子问题（如下所述）。
超级问题解决方案说明
给定平面上的两个点 X=(x1,x2) 和 Y=(y1,y2) - 如果平面包含障碍物/区域，从 X 到 Y 的最短路径是什么路径不能引导？
不同/更直观假设他不能翻墙或走路，从Link的当前位置到地图上第二个红点的最短路径是什么穿过灌木丛？
这个问题通常被称为二维情况下的Eucledian Shortest Path Problem and can be solved in Polynomial time。太棒了！
为了实现这一点，在它连接的点之间有一个所谓的 Visibility Graph with V= {X,Y} U {"Corner-Points of obstacles}" is constructed. Edges are inserted between points P and Q if and only if it is possible to draw a straight line from P to Q without crossing any obstacle. Each edge is weighted by the Eucledian Distance。
在上面的示例中，可见性图表看起来像这样。为了便于阅读，我省略了一些边和权重。阴影区域表示障碍。
然后可以在可见性图上使用开发人员最喜欢的最短路径算法计算最短路径。
子问题描述
让我们首先将障碍物定义为不可通行地形的连续区域。如何找到所有障碍物所需角点的最少数量（以及角点的坐标）以构建执行最短路径计算所需的最小可能可见性图？
对于矩形障碍物，很容易找到拐角，因为只有少数锐边，如图所示...
...或应用于游戏场景
然而，一旦障碍物具有对角线“正面”，由于诱导的拼图图案（无论角度如何），获得角点变得非常重要。下面的截图说明了这个问题：左手边的图片显示了哪些坐标点应该被识别为角，而右手边的图片显示了由于对角线的“拼图”模式，额外的点将被插入的位置。
现在的问题是：如何排除/防止这些不必要的角点（插入到）可能非常大的可见性图中？
看看每个点周围的点怎么样，如果你发现两个点完全相反但不交叉 "solid" 那么你就知道你实际上有一个移除候选者。在删除任何点之前对所有点执行此操作，然后一次性删除所有这些候选点。
这将处理水平、垂直和对角线。如果将半径扩展到两个或更多，您还可以检测到其他角度 "lines" 上的冗余点。
时间复杂度几乎是 O(n)（当 n 是点数时），因为您将检查每个点周围固定数量的点以找到移除候选者，例如：
每个点要检查的半径 1 - 4 个相邻点对：
123
4X5
678
=> 检查对 (1 8), (2 7), (3 6), (4 5)
半径 2 - 每个点要检查的 8 个相邻点对：
1 2
34567
8X9
ABCDE
F G
=> 检查对 (1 G), (2 F), (3 E), (4 D), (5 C), (6 B), (7 A), ( 8 9)