高效算法确定最大开放空间

Question

高效算法确定最大开放空间

8

我有一个情况，如下图所示，需要我计算出一个区域内最大的圆形（空白区域）。在下面的例子中，黑色圆圈是固定的已知位置，我需要找到最大的区域（由橙色和绿色圆圈表示），它们不与黑色圆圈接触。在下面的例子中，橙色圆圈是最大的空白区域，这是我想要计算的区域。

我可以用蛮力法，选择一个位置并扩展圆形，直到它碰到黑点，然后记录圆的位置和半径（开放空间），但这将极其低效，需要迭代所有可能的位置。在这种情况下，有没有一种有效的方法来分析最大开放空间在哪里？请注意，该场地上的黑点最多为15个，但实际上可能会少得多。

编辑：感谢Yves和所有其他评论者。根据答案和其他评论，有几点需要澄清。黑盒子是一个边界，因此任何定义的区域必须在黑盒子内部。黑色圆圈的半径已知且静态，但在这些目的下，它们可以缩小为点。最后，圆的近似是可以接受的。它将用于具有决定最佳区域误差范围的AI例程。因此，如果圆的半径或位置略有偏差，也不会有太大问题。

我目前正在研究沃罗诺伊方法，我想我理解了它，但现在尝试找到适合的算法是一个问题！我会测试并回复您。 编辑2：感谢Yves，我研究了Voronoi图，并使用了一个简单的方法循环遍历所有Voronoi顶点（以及它穿过边界框的点），并找到从该中心点开始不包含任何“黑色圆”的最大圆。对于一个相对较小的、有限的点集，我对这个实现感到满意。请参见下面的结果，显示空间中前3个空圆。

- anothershrubery

黑色的盒子也是一个边界吗？还是彩色的圆只应该被黑色的圆所限制？ - Adam

所有的黑色圆圈半径都一样吗？ - Adam

我感觉右边的某个地方比橙色圆圈所在的地方有更多的开放空间。 - OneCricketeer

1

以下精彩的插图展示得非常好笑。 - UmNyobe

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1196549 · Accepted Answer

这被称为“最大空圆”问题。可以通过 Voronoi 图解决它。

如果黑色圆有有限的直径，您可以将它们缩小到它们的中心，然后从找到的解中推导出半径。

无论如何，如果允许圆与矩形相交，算法必须修改以考虑此情况，这是一个非常复杂的任务。

更新：

在 "TOUSSAINT, Godfried T. Computing largest empty circles with location constraints. International journal of computer & information sciences, 1983, 12.5: 347-358" 和 "CHEW, L. Paul; DRYSDALE, Scot. Finding largest empty circles with location constraints. 1986." 中提出了一个相关问题的解决方法，当圆心被限制在给定凸多边形内时，可以高效地解决此问题。（但我想你是要求圆完全包含在多边形内。）

在数字领域（处理离散图像、大小有限的像素），可以计算到黑像素的欧氏距离映射。有一种非常聪明有效的算法可以线性时间（相对于图像大小而不是障碍物数量）实现这一点，请参见“A. Meijster、J.B.T.M. Roerdink 和 W.H.Hesselink，A general algorithm for computing distance transforms in linear time”。

计算了距离映射后，所需圆的中心是具有最大距离值的像素。此方法适用于任何形状的障碍物。

更新：

在您的情况下，由于障碍物数量较少，穷举搜索可能是可以接受的。您需要尝试通过 3 个点/穿过 2 个点并与一条边相切/通过 1 个点并与 2 条边相切来构建圆。

对于所有这些圆，检查它们是否不包含其他点，并保留最大的。原则上，这需要 O(N^4) 的时间。显然，这个复杂度可以降至 O(N³)，但我找到的每个涉及此问题的条目都描述了基于 Voronoi 的方法而不是穷举法。