algorithm - 如何用固定数量的圆圈部分覆盖给定的形状？

Question

我不确定在这里寻求算法方面的帮助是否合适，但谁能给我一些指导，或者告诉我在哪里可以找到这样的指导？非常感谢！

问题是这样的：给定固定数量的圆，我需要一种算法来找到这些圆的最佳位置和半径以覆盖给定形状，因此误差区域（给定形状之外的圆部分 +这些圆圈未覆盖的形状部分）是最小的吗？圆圈可能重叠。

Answer 1

这不是一个微不足道的问题，当然也没有简单的分析解决方案。例如：即使是最简单的版本——一个圆和一个简单的连通区域也不一定容易解决，具体取决于区域的形状。通常还会有许多错误的最小值。

我建议模拟退火将是一种合适的技术来找到一个好的（如果不是最优的）解决方案。实际上，使用 n 个圆，您正在探索 3n 个变量（每个圆的 x、y 和 r）的变化很大的函数，而模拟退火是探索这种环境的一种相当有效的方法。