确定最大开口的高效算法 space
Efficient algorithm to determine largest open space
我有一种情况，如下图所示，它要求我计算出一个区域内最大的圆圈（空心 space）。在下面的示例中，黑色圆圈是固定的已知位置，我需要找到不接触黑色圆圈的最大区域（由橙色和绿色圆圈表示）。在下面的例子中，橙色圆圈是最大的开放区域 space，这是我要计算的区域。
我可以暴力破解它，选择一个位置并扩大一个圆圈直到它碰到一个黑点，然后只记录圆圈的位置和半径（open space）但这将是巨大的遍历所有可能的位置效率低下。
在这种情况下，是否有一种有效的方法来分析最大的开放 space 在哪里？请记住，该字段的最大黑点数为 15，但可能会低很多。
编辑 感谢 Yves 和所有其他评论者。基于答案和其他评论的一些澄清。黑框是一个边界，所以定义的任何区域都必须在黑框内。黑色圆圈的半径是已知的并且是静态的，但是为了这些目的，它们可以减少为点。最后，圆的近似是可以接受的。它将用于 AI 例程，该例程在决定哪个区域最好时有一定的误差范围。所以，如果圆圈的半径或位置略微偏出，问题不大。
我目前正在研究 Voronoi 方法，我想我理解它，但现在尝试提取适合的算法才是问题所在！我会测试并回复你。
编辑 2：多亏了 Yves，我查看了 Voronoi 图并使用了一种简单的方法来遍历所有 Voronoi 顶点（以及它穿过边界框的点）并找到从该中心点开始的最大圆，不包含任何 "black circles"。对于相对较小的有限点集，我对这个实现很满意。查看下面的结果，在 space.
中显示前 3 个空心圆圈
这被称为 "largest empty circle" 问题。借助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 and W. H. Hesselink, A general algorithm for computing distance transforms in linear time"。
计算出距离图后，所需圆的中心就是距离值最大的像素。此方法适用于任何形状的障碍物。
更新:
在你的情况下，由于障碍物的数量较少，穷举搜索可能是可以接受的。您需要尝试通过 3 个点的圆，通过 2 个点并与一条边相切，或者通过 1 个点并与 2 个边相切。
对于所有这些圆，检查它们是否不包含其他点并保持最大。原则上，这需要时间 O(N^4)。显然，这种复杂性可以降低到 O(N³)，但我在这个问题上找到的每个条目都描述了基于 Voronoi 的方法，而不是详尽的方法。
我有一种情况，如下图所示，它要求我计算出一个区域内最大的圆圈（空心 space）。在下面的示例中，黑色圆圈是固定的已知位置，我需要找到不接触黑色圆圈的最大区域（由橙色和绿色圆圈表示）。在下面的例子中，橙色圆圈是最大的开放区域 space，这是我要计算的区域。
我可以暴力破解它，选择一个位置并扩大一个圆圈直到它碰到一个黑点，然后只记录圆圈的位置和半径（open space）但这将是巨大的遍历所有可能的位置效率低下。
在这种情况下，是否有一种有效的方法来分析最大的开放 space 在哪里？请记住，该字段的最大黑点数为 15，但可能会低很多。
编辑 感谢 Yves 和所有其他评论者。基于答案和其他评论的一些澄清。黑框是一个边界，所以定义的任何区域都必须在黑框内。黑色圆圈的半径是已知的并且是静态的，但是为了这些目的，它们可以减少为点。最后，圆的近似是可以接受的。它将用于 AI 例程，该例程在决定哪个区域最好时有一定的误差范围。所以，如果圆圈的半径或位置略微偏出，问题不大。
我目前正在研究 Voronoi 方法，我想我理解它，但现在尝试提取适合的算法才是问题所在！我会测试并回复你。
编辑 2：多亏了 Yves，我查看了 Voronoi 图并使用了一种简单的方法来遍历所有 Voronoi 顶点（以及它穿过边界框的点）并找到从该中心点开始的最大圆，不包含任何 "black circles"。对于相对较小的有限点集，我对这个实现很满意。查看下面的结果，在 space.
中显示前 3 个空心圆圈这被称为 "largest empty circle" 问题。借助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 and W. H. Hesselink, A general algorithm for computing distance transforms in linear time"。
计算出距离图后，所需圆的中心就是距离值最大的像素。此方法适用于任何形状的障碍物。
更新:
在你的情况下，由于障碍物的数量较少，穷举搜索可能是可以接受的。您需要尝试通过 3 个点的圆，通过 2 个点并与一条边相切，或者通过 1 个点并与 2 个边相切。
对于所有这些圆，检查它们是否不包含其他点并保持最大。原则上，这需要时间 O(N^4)。显然，这种复杂性可以降低到 O(N³)，但我在这个问题上找到的每个条目都描述了基于 Voronoi 的方法，而不是详尽的方法。