我有一种情况，如下图所示，它要求我计算出一个区域内最大的圆圈(开放空间)。在下面的示例中，黑色圆圈是固定的已知位置，我需要找到不接触黑色圆圈的最大区域(由橙色和绿色圆圈表示)。在下面的示例中，橙色圆圈是最大的开放空间，这是我要计算的面积。
我可以暴力破解它，选择一个位置并扩大一个圆圈直到它碰到一个黑点，然后只记录圆圈(开放空间)的位置和半径，但这将非常低效地遍历所有可能的职位。
在这种情况下，是否有一种有效的方法来分析最大的开放空间在哪里？请记住，该字段的最大黑点数为 15，但可能会低很多。
编辑 感谢 Yves 和所有其他评论者。基于答案和其他评论的一些澄清。黑框是一个边界，所以定义的任何区域都必须在黑框内。黑色圆圈的半径是已知的并且是静态的，但是为了这些目的，它们可以减少为点。最后，圆的近似是可以接受的。它将用于 AI 例程，该例程在决定哪个区域最好时有一定的误差范围。因此，如果圆圈的半径或位置略微偏出，则不会成为大问题。
我目前正在研究 Voronoi 方法，我想我理解它，但现在尝试提取适合的算法才是问题所在!我会测试并回复您。
编辑 2:多亏了 Yves，我研究了 Voronoi 图并使用了一种简单的方法来遍历所有 Voronoi 顶点(以及它穿过边界框的点)并从中找到最大的圆不包含任何“黑圈”的中心点。对于相对较小的有限点集，我对这个实现很满意。请参阅下面的结果，显示空间中的前 3 个空心圆圈。
最佳答案
这被称为“最大的空圆”问题。借助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”中得到解决. 寻找具有位置限制的最大空心圆圈。1986 年。”当中心被限制在给定的凸多边形内时，它描述了一种有效的解决方案。 (但我想你是在要求完全包含圆圈。)
在数字领域(处理离散图像、有限大小的像素)可以采用完全不同的方法:您可以计算到黑色像素的欧几里德距离图。有一种非常聪明的高效算法可以在线性时间内实现这一点(关于图像大小，而不是障碍物的数量)；参见“A. Meijster、J. B. T. M. Roerdink 和 W. H. Hesselink，一种在线性时间内计算距离变换的通用算法”。
计算出距离图后，所需圆的中心就是具有最大距离值的像素。此方法适用于任何形状的障碍物。
更新:
在您的情况下，由于障碍物的数量很少，穷举搜索可能是可以接受的。你需要尝试圆通过 3 个点，通过 2 个点并与一条边相切，或者通过 1 个点并与 2 个边相切。
对于所有这些圆，检查它们是否不包含其他点并保留最大的。原则上，这需要时间 O(N^4)。显然，这种复杂性可以降低到 O(N³)，但我在这个问题上找到的每个条目都描述了基于 Voronoi 的方法，而不是详尽的方法。
关于algorithm - 确定最大开放空间的高效算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34093602/