检查 Circle 是否适合穿过非量化 2d 中的迷宫 space

Question

我是一名高中生，最近参加了一个编码竞赛，遇到了这个我不知道如何解决的问题：

给定一个封闭在 100x100 区域中的迷宫，根据所有墙壁的位置，确定具有给定半径的圆是否可以穿过迷宫。墙将被定义为连接 space 内两点的线，您将获得圆的起点和终点。圆圈必须从起点的圆心开始并接触终点才能成功穿过迷宫。最多将有 20 面墙。圆的半径和墙壁的位置可以 "arbitrarily" 精确。（对于这种情况，"arbitrarily" 仅表示在很远的范围内 - 比方说，小数点后最多 10 位）。

这是一个例子。如果这是输入：

Radius = 2.8
Start = (5,5), Destination = (95,95)
Walls (a wall connects each pair of points):
(20,0) to (27.5,22.6)
(27.5,22.6) to (55.1,35.5)
(55.1,35.5) to (80.3,80,4)
(80.3,80,4) to (95,63.9)
(1.7,25.8) to (17.5,53.2)
(17.5,53.2) to (56.4,69)
(56.4,69) to (67.9,90.6)
(85.6,98.94512) to (87.3,92.5)

那么这个（在desmos上制作）就是迷宫的样子（蓝色圆圈只是为了显示圆圈有多大）：

如果在量化网格中我会知道如何解决问题，但墙壁的确切位置和圆的半径可以任意精确。我考虑过使用 "right-hand rule" 来查找路径，但我不知道如何在非量化 space 中实现它（我也不太熟悉该方法）。

我将如何解决这个问题？有人能给我指出一个算法、一个 link、一些伪代码，或者只是一种可以帮助我理解如何解决这个问题的直觉吗？任何帮助表示赞赏。谢谢！

Answer 1

这是一项艰巨的任务，而且编码起来并不容易，但这是一种行之有效的方法：

设r为圆的半径。这意味着圆的 center 不能进入任何障碍物的 r.

将迷宫区域的墙壁每边移动 r。

用半径为 r 的圆替换每个墙端点。

用宽度为 2r.

的矩形替换每面墙

现在您无需担心圆圈 -- 只需担心它的中心点，该中心点必须保持在新边界内，并且在您根据墙壁制作的任何圆圈或矩形之外。

现在，如果他们在同一个封闭区域内，就有一条从头到尾的路径。找出答案...

在每个交叉点和垂直最大值或最小值处水平切割场景以创建条带，每个条带由一直穿过它的直线或圆弧划分为多个区域。区域不将方向连接到其左侧和右侧的区域，但可以连接到其上方和下方条带中的零个或多个区域。区域之间的连接形成一个图。

从包含起点的区域开始，运行在此图上进行 BFS 或 DFS，看看是否可以到达包含终点的区域。

Answer 2

Thickennig/moving 墙由 r 在每一侧，就像在另一个答案中一样（+1 btw）听起来很简单，但对其进行编码并非易事。有关详细信息，请参阅

draw outline for some connected lines

如果 dx,dy 是直线方向，那么 2D 中的法线方向很容易，然后 (-dy,dx) 和 (dy,-dx) 是它的法线 ...

但是我鼓励通过计算迷宫的每个顶点到墙的最近距离和比 2r ...

像这样：

所以：

每个顶点
检查所有不属于顶点路径的线
计算到直线及其顶点的垂直距离和最小距离 d 使用最小的 d 距离可以很容易地计算出来见：
只需在那里寻找 Perpendicular distance of any point P to AB 所以：
```
d = min
      (
      perpendicular_distance(line,vertex), 
      |line_vertex1-vertex|, 
      |line_vertex2-vertex| 
      )
```
if d<2r 关闭路径。例如，通过添加一条连接墙的线，它离测试顶点太近了

理想情况下通过连接测试的顶点和找到的最近点。不要忘记在这种情况下将对面的墙线按最近点一分为二，这样您的图形算法仍然有效...

如您所见，这是 O(n^2) 而不是另一个答案中的 O(n) 但它的证明是错误的......扩大多边形不是，事实上它是最难的事情之一在 2D 几何中进行编码（IIRC 甚至还有未解决的问题）...

检查 Circle 是否适合穿过非量化 2d 中的迷宫 space

Check if a Circle fits through a maze in non-quantized 2d space

algorithm

search

2d

maze