用等半径的圆覆盖任意区域

Question

算法如何工作覆盖半径相等的圆的任意区域？

圆的半径和区域的大小和形状是任意给出的.该区域应尽可能少地覆盖.圆圈可能重叠.

有算法可以处理吗？

Answer 1

我知道这个问题可能有点过时了，但最近我遇到了一个类似的问题，即使用六边形网格用相等的圆圈覆盖地理区域，这就是我解决的方法：

1. 我的输入数据是以米为单位给出的圆半径和该区域边界的坐标
2. 首先我找到了覆盖给定区域的边界矩形
3. 然后从左下角开始，我移动点的距离等于用于构建六边形的三角形高度的两倍（它的边与我的圆的半径相同）和使用文森蒂公式的 0 度方位角
4. 对于我找到的每个点，我检查它是否与我的输入区域相交，如果我保存它，其他方式我跳过它
5. 当我到达边缘时，我再做一次检查，以确保我将获得范围内的所有分数
6. 我通过 60 度的方位移动点，检查它，然后 120 度，再次检查
7. 回到第 3 步，但现在我通过 180 度的方位移动这些点
8. 然后边缘再检查一次，然后像第 6 步一样，但首先是 120 度，然后是 60 度
9. 继续直到到达矩形的顶部边缘

就像在给定的图像中一样，当然您可以通过减小圆的半径来提高精度

我知道这不是最好的选择，但它对我来说效果很好。

我希望它很容易理解，并会帮助任何人。

Answer 2

希望我理解你的问题吧...

可以证明球体的六边形密堆积(HCP)使用球体覆盖最大体积.因此,我假设用圆圈做HCP也会用圆圈覆盖最大区域.使用三角形对您的区域进行细分,并在三角形的每个顶点放置一个圆心,其中心半径为三角形边长的一半.请参阅此图,了解我正在讨论的算法的图像.

注意:这类似于晶胞中原子的紧密堆积.

编辑:我以前的方法涵盖了尽可能多的区域,没有重叠.如果允许重叠,那么(我相信)以下方法将覆盖整个区域,并且重叠最小.

您可能知道,只有3个具有正多边形的2D空间镶嵌 - 使用正方形,三角形或六边形.策略是使用这些多边形中的一个进行镶嵌,然后将圆圈限定为每个多边形.使用这种方法六边形会浪费最小面积.

因此,从给定圆的半径,计算所需六边形的大小,使用六边形镶嵌区域,然后在每个六边形上限定一个圆.

NB: Eric Bainville提出了类似的方法.

-- Flaviu Cipcigan

Answer 3

在不了解更多关于您的约束的情况下，我建议对平面进行常规覆盖，其中圆盘对应于六边形平铺的正六边形。然后保持所有圆盘与形状相交。