覆盖有n个重叠圆圈的广场

Question

有n个相同的圆圈和一个square.How我可以随机放置在广场内的圆圈，使广场完全覆盖？ PS：所有圈子应该与其他圈子重叠。

Answer 1

您可以尝试一种随机方法，例如，某种evolutionary algorithm。在最简单的形式：

• 将您ň圈半径[R随机在广场
• 测量的广场上，例如那些圈的覆盖范围通过采样一些（或相当多）点，并测试它们是否对任何圆
• 重复，直到方被完全覆盖（或直到X代已通过）的[R内：
  • 略有不同通过随机移动一个或多个圆圈来覆盖
  • 测量新变体的覆盖范围如果新变体的覆盖范围比原始范围好，请保留变体，否则保留原始的下一个迭代

请注意，这不能保证始终找到最佳解决方案（如果有的话），但它在一般情况下应该工作得相当好。另外，为了防止提前终止（或找到更好的确定性方法），您可能需要抽取相当多的点数，或者一旦覆盖率变得相当高，您可以动态增加要采样的点数。

PS .:你的PS不需要检查。如果圆圈不重叠，则无法覆盖矩形的整个区域而没有间隙。