寻找一组点中最宽的空直线路径

Question

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

我想知道是否有任何有效的算法来解决这个问题？您能否提供与此问题相关的关键词/论文/任何信息？

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

- Chan Le

---

也许你可以找到一些涉及Delaunay三角剖分的东西。 - JoshRoss

从哪里到哪里的路径？ - Dr. belisarius

@belisarius 从矩形外部穿过矩形到达矩形外部。 - Chan Le

Answer 1

这是最宽的空走廊问题。Houle和Maciel在1988年的技术报告中提供了一种O(n²)时间复杂度、O(n)空间复杂度的算法，题为“通过一组点找到最宽的空走廊” ，但似乎在网上不可用。幸运的是，Janardan和Preparata在他们的论文 Widest-corridor problems的第4节中描述了这个算法，该论文可供使用。

- some guy

---

这对我来说似乎相当复杂 :( 你能否给我解释一下这个算法？ - Chan Le

Answer 2

遍历所有点对。通过这些点构造一条直线 l。(^1) 在 l 的每一侧，要么有其他的点，要么没有。如果没有，则该侧没有路径。如果存在其他点，则遍历这些点并计算从 l 到每个点的垂直距离 d。记录最小的 d，那就是该侧上最宽的路径。继续遍历所有点对，比较该点对的最宽路径和以前的最宽路径。

这种算法可以被认为是天真的，运行时间为O(n^3)。 编辑：以上算法忽略了一种情况。在 ^1 处插入：“通过每个点对的每个点构造两条垂直于 l 的直线。如果没有第三个点在两条线之间，则记录点之间的距离 d。这形成了一条路径。” 然后继续算法。增加额外的情况后，算法仍然是O(n^3)。

- ThomasMcLeod

---

我认为这个算法在等边三角形的情况下不起作用。它会返回底边的一半作为最宽的路径，而不是高度。 - Cephron

@Cephron，嗯不是的。它会返回三个不同方向的高度。这个算法不受点的方向影响。线路，因此路径，由前两个点确定，它们可以是彼此的任何方向。 - ThomasMcLeod

啊！是的，我现在明白了。我以为你的意思是点对之间的路径，而不是点对两侧的路径。我的错误！ - Cephron

你需要三个点来确定路径。但是，我认为有一种情况，当一对点也可以确定路径。http://i.imgur.com/Zc57K.png - Chan Le

@Chan，谢谢，我漏掉了那个。我添加了额外的情况。 - ThomasMcLeod

Answer 3

我个人会从点集的Delaunay三角剖分开始看起： http://en.wikipedia.org/wiki/Delaunay_triangulation

这里似乎有很多关于高效算法构建它的资源 - 例如O(n log n)的Fortune算法。

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

编辑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)。好在，对于一般的随机点集，我们不需要遍历所有的边。

- Cephron

---

如果你的等边三角形在一个矩形内部，你必须包括矩形的边界，这样你就会得到八个三角形和12条边。其中肯定有一条边是垂直于解决方案的。 - JoshRoss