提问人：John 提问时间：5/9/2019 最后编辑：saastnJohn 更新时间：11/20/2020 访问量：274
如何在具有恒定半径的不相交圆的平面中覆盖一组圆？
How to cover a set of circles in a plane with disjoint circles of constant radius?
问：
因此，您有一个给定尺寸的图纸/区域，并且该区域内有孔（给出了它们的中心点（x，y）和半径）。问题是你需要用补丁覆盖这些孔。这些圆形斑块的半径是固定的（即：半径为5），不允许相互重叠（但可以接触）。你可以随心所欲地使用，目标不是找到最佳数量，而是看看是否有可能覆盖每一个洞。
我已经用 KD 树解决了一个类似的问题，但由于这个问题中孔的 3D 维度性质，我不确定如何处理它。只是在寻找正确方向的指针，而不是编码的解决方案:)
答：
1赞
Ripi2
5/10/2019
#1
根据贴片和孔的大小，可能没有解决方案。
具有最紧凑的补丁阵列的解决方案：
没有解决方案，因为孔比补丁大，这允许未覆盖的区域：
没有解决方案，因为孔太近了：
对于一般结构，您从以孔为中心的补丁开始。然后根据需要平移和旋转（围绕连续贴片的中心）贴片：
评论
0赞
John
5/10/2019
干杯。这是否也适用于用单个补丁覆盖多个孔？假设每个孔的半径为 1-3，而面片的半径为 5？
1赞
saastn
5/13/2019
#2
您可能正在寻找一个分析性或至少一个确定性的解决方案。但恐怕有一个太复杂了。另一方面，像 EAs 这样的元启发式方法由于其随机性而可以应对此类问题。当您决定采用这种方法时，您必须将问题更改为优化问题。
我尝试使用基本形式的 DE 算法来解决这个问题。为了定义一个优化问题，我假设一个解向量是一个浮点变量数组，其中是孔的数量。此数组表示面片的坐标，因为最多需要面片来覆盖孔。2*NNXYNN
成本函数（最小化所需的）定义如下：
Find closest patch to each hole
Find A1 as sum of uncovered areas of holes by their closest patchs
Find A2 as sum of intersection areas of active(!) patches
return max(A1, A2)
在此函数中，活动贴片是最接近至少一个孔的贴片。这个定义被添加到问题中，以涵盖您在对 Ripi2 答案的评论中提到的情况（当一个补丁覆盖两个孔时，所以还有另一个补丁是无用的）。为了更具描述性，让我们假设这个补丁不是最接近任何孔的补丁。 是离这个补丁最近的孔，但它最近的补丁是 。因此，我们可以肯定地说，和的交集面积小于或等于 和 的交面积。由于它最近的孔是正确的，所以所有其他孔都是一样的，所以让我们假设它不存在！P1H1P2H1P1H1P2
这是一个示例：
请记住，这些算法永远无法保证找到全局最优，但是，它们会给出一组次优解。
评论