以下问题:
给定的是一个任意多边形。它应以给定半径的最小圆数覆盖 100%。
注意:
1)自然地，圆圈必须重叠。
2)我尝试解决任意多边形的问题。但也赞赏CONVEX多边形的解决方案。
3) 据我所知，这个问题是 NP-hard ( an algorithm to find the minimum size set cover for the Set-cover problem )
选择: U = 多边形和 S1...Sk = 具有任意中心的圆。
我的解决方案:
我已经阅读了一些论文并自己尝试了一些东西。我想出的最有前途的想法实际上是 Covering an arbitrary area with circles of equal radius 中已经指出的一个。
所以我想最好是我快速尝试描述我自己的想法，然后完善我的问题。
这张照片已经让你对我所做的事情有了一个很好的了解
IDEA 和问题表述
1. 我用相应的六边形近似圆并镶嵌整个 R2，即足够大的区域；关键字六边形最接近的包装。 (青色……镶嵌，红色虚线，青色六边形的中心)
2. 我把多边形放在这个镶嵌区域中间的某个地方，并计算覆盖多边形所需的六边形数量。
在下面，我试图通过在每一步“计数”N 之后逐步移动多边形来最小化 N，即覆盖多边形所需的六边形数量。
解决问题:
所以这就是它变得困难的时候(对我来说)。我不知道有任何优化器可以正确解决这个问题，因为它们都在稍微移动多边形并且没有观察到任何变化后终止。
我的解决方案如下:
首先请注意，这是一个周期性问题:
1.多边形可以在水平方向x上以六边形的3*r(边长=半径r)为周期移动。
2.多边形可以以六边形的r^2+r^2-2*rrcos(2/3*pi)的周期在垂直方向y上移动。
3.多边形可以以2/3*pi的周期旋转phi。
这意味着，必须搜索可能解决方案的有限区域才能找到最佳解决方案。
所以我所做的是，我为 (x,y,phi) 选择一个步长，然后简单地强力计算所有可能的解决方案，挑选出最佳解决方案。
完善我的问题
1) 问题的表述是否明智？现在我正在研究一种只分割一个非常小的区域的算法，因此必须计算尽可能少的六边形。
2)有没有更智能的优化器来解决问题？
3)最后:我也很难找到合适的文献，因为我不知道我不知道要寻找的正确关键词。因此，如果有人可以提供我的文献，也将不胜感激。
实际上我可以继续我尝试过的其他事情，但我认为你们中没有人愿意花一整个下午来阅读我的问题。
提前感谢所有花时间考虑的人。
垫
PS我在matlab中实现我的算法
最佳答案
编辑: 答案重写(没有限制，圆圈不能超出多边形)。
您可能对 Covering a simple polygon with circles 感兴趣。我认为该算法也适用于或可扩展到复杂的多边形。
关于matlab - 用给定直径的最少圆数覆盖多边形，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10648621/