algorithm - 通过一组点找到最宽的空直路径

Question

我正在创建一个简单的游戏，并在为我的游戏设计 AI 时遇到了这个问题：给定笛卡尔坐标中一个矩形内的一组 N 个点，我需要找到通过这个矩形的最宽的直线路径。路径必须为空（即不包含任何点）。

我想知道是否有任何有效的算法来解决这个问题？你能推荐任何与这个问题相关的关键字/论文/任何东西吗？

编辑：矩形总是由其角落的 4 个点定义。我添加了一张图片用于说明。上图中的路径由两条红线确定

Answer 1

这是最宽的空走廊问题。Houle 和 Maciel 在 1988 年题为“通过一组点找到最宽的空走廊”的技术报告中给出了 O(n ² )-时间、O(n)-空间算法，该算法似乎无法在线获得。幸运的是，Janardan 和 Preparata 在他们的论文Widest-corridor questions 的第 4 节中描述了这个算法，该论文是可用的。

Answer 2

循环遍历所有点对。通过该对构造一条线l 。(^1) 在l的每一边，要么有其他点，要么没有。如果不是，则l的那一侧没有路径。如果还有其他点，则遍历计算从l到每个这样的点的垂直距离d的点。记录最小值d。那是l那边最宽的路径。继续遍历所有对，将该对的最宽路径与之前的最宽路径进行比较。

该算法可以被认为是幼稚的并且可以O(n^3)及时运行。

编辑：上述算法遗漏了一个案例。在上面的 ^1 处，插入：“通过该对的每个点构造两条垂直于l的线。如果线之间没有第三点，则记录点之间的距离d。这构成了一条路径。” 在 ^1 处继续算法。加上额外的情况，算法仍然是O(n^3)

Answer 3

我自己，我将首先查看点集的 Delaunay 三角剖分： http ://en.wikipedia.org/wiki/Delaunay_triangulation

那里似乎有大量资源可用于构建此算法的高效算法—​​—Fortune 的算法，初始时间为 O(n log n)。

我的直觉告诉我，您最宽的路径将由该图中的一条边定义（即，它将垂直于边，其宽度将等于边的长度）。如何对边缘进行排序、检查候选并确定最宽的路径。我喜欢这个问题，我会继续思考这个问题。:)

编辑1：我的直觉让我失望！一个简单的等边三角形就是一个反例：最宽的路径比三角剖分中的任何边都短。仍然在想...

编辑2：所以，我们需要一个黑盒算法，给定集合中的两个点，找到通过以这两个点为界的点集的最宽路径。（想象两条穿过两点的平行线；将它们相互协调地旋转，直到它们之间没有点）。让我们将此算法的运行时间称为“R”。

给定这样的算法，我们可以执行以下操作：

1. 构建点集的 Delaunay 三角剖分：O(n log n)
2. 按宽度对边缘进行排序：O(n log n)
3. 从最大边开始向下移动，使用黑盒算法确定涉及这两个点的最宽路径；将其存储为 X : O(nR))
4. 当被检查的边短于 X 的宽度时停止。

第 1 步和第 2 步很好，但 O(nR) 有点吓人。如果 R 结果是 O(n)，那么整个算法已经是 O(n^2)。好消息是，对于一组一般的随机点，我们希望我们不必遍历所有边缘。