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

Question

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

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

Answer 1

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

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