覆蓋有n個重疊圓圈的廣場

Question

有n個相同的圓圈和一個square.How我可以隨機放置在廣場內的圓圈，使廣場完全覆蓋？ PS：所有圈子應該與其他圈子重疊。

Answer 1

您可以嘗試一種隨機方法，例如，某種evolutionary algorithm。在最簡單的形式：

• 將您ň圈半徑[R隨機在廣場
• 測量的廣場上，例如那些圈的覆蓋範圍通過採樣一些（或相當多）點，並測試它們是否對任何圓
• 重複，直到方被完全覆蓋（或直到X代已通過）的[R內：
  • 略有不同通過隨機移動一個或多個圓圈來覆蓋
  • 測量新變體的覆蓋範圍如果新變體的覆蓋範圍比原始範圍好，請保留變體，否則保留原始的下一個迭代

請注意，這不能保證始終找到最佳解決方案（如果有的話），但它在一般情況下應該工作得相當好。另外，爲了防止提前終止（或找到更好的確定性方法），您可能需要抽取相當多的點數，或者一旦覆蓋率變得相當高，您可以動態增加要採樣的點數。

PS .:你的PS不需要檢查。如果圓圈不重疊，則無法覆蓋矩形的整個區域而沒有間隙。