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

我有一个情况,如下图所示,这需要我找出一个区域内最大的圆圈(开放空间).在下面的例子中,黑色圆圈是固定的已知位置,我需要找到不接触黑色圆圈的最大区域(由橙色和绿色圆圈表示).在下面的例子中,橙色圆圈是最大的开放空间,这是我想要计算的区域.

我可以强行它,选择一个位置并展开一个圆圈,直到它碰到一个黑点,然后只记录圆的位置和半径(开放空间),但是迭代所有可能的位置将会非常低效.

有没有一种有效的方法来分析这种情况下最大的开放空间在哪里？请记住,此字段上的最大黑点数将为15,但可能会低很多.

编辑感谢Yves和所有其他评论者.根据答案和其他评论做出的一些澄清.黑盒子是绑定的,因此定义的任何区域必须在黑盒子内.黑色圆圈的半径是已知的并且是静态的,但是出于这些目的,它们可以减少到点.最后,圆的近似是可以接受的.它将用于AI例程中,该例程在确定哪个区域最佳时具有误差范围.因此,如果圆圈的半径或位置略微偏离,那么这不是一个大问题.

我目前正在研究Voronoi方法,我想我理解它,但现在尝试拉出适合的算法就是问题!我会测试并回复你.

编辑2:感谢Yves我查看了Voronoi图并使用了一种简单的方法来循环遍历所有Voronoi顶点(以及它穿过边界框的点)并找到该中心点的最大圆圈,该圆圈不包含任何"黑圈".使用相对较小的有限点集,我很满意这个实现.请参阅下面的结果,显示空间中的前3个空心圆.

这被称为"最大的空心圆"问题.它可以通过Voronoi图有效地解决.

如果黑色圆圈的直径有限,您可以将它们缩小到中心,然后从找到的解决方案中推导出半径.

无论如何,如果允许圆圈对着矩形,则需要修改算法以解决此问题.一项非常重要的任务.

更新:

一个相关的问题在"TOUSSAINT,Godfried T.计算最大空圈和位置限制."国际计算机与信息科学杂志,1983,12.5:347-358"和"CHEW,L.Paul; DRYSDALE,Scot.查找最大有位置限制的空心圈.1986." 当中心被约束在给定的凸多边形内时,它描述了一种有效的解决方案.(但你要求圈子完全包含在我猜中.)

在数字域中可以采用完全不同的方法(处理离散图像,有限大小的像素):您可以计算欧几里德距离映射到黑色像素.有一种非常智能的高效算法可以在线性时间内实现(图像大小,而不是障碍物的数量); 参见"A. Meijster,JBTM Roerdink和WH Hesselink,一种计算线性时间距离变换的通用算法".

计算出距离图后,所需圆的中心是距离值最大的像素.这种方法适用于任何形状的障碍物.

更新:

在您的情况下,由于障碍物的数量很少,因此可以接受详尽的搜索.您需要尝试通过3个点的圆圈,经过2个点并与边缘相切,或者经过1个点并切线到2个边缘.

对于所有这些圈子,检查它们是否包含其他点并保持最大值.原则上,这需要时间O(N ^ 4).显然,这种复杂性可以降低到O(N³),但我在这个问题上找到的每个条目都描述了基于Voronoi的方法而不是详尽的方法.