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

Question

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

圆的半径以及区域的大小和形状是任意给定的。该区域应覆盖尽可能少的圆圈。圆圈可能会重叠。

有没有一种算法可以处理这个问题？

Answer 1

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

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

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

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

我希望它很容易理解并且对任何人都有帮助。