用不同大小的圆包装不规则多边形

Question

我正在尝试使用 Shapely 在 Python 中编写一个程序，该程序接收形状文件（现在是国会选区）并 "packs" 它们带有圆圈。最终目标是获得圆的中心点和半径。我想用最少的圆圈覆盖最大的区域。

到目前为止，我通过 Google 找到的所有资源都是关于标准几何对象（如 squares/circles/triangles 等）内的圆形包装...所以我的直觉是尝试将这些形状变成三角形或其他东西，然后将一些现有算法应用于更简单的形状。

如果形状有很多小的凹边，这看起来是解决问题的正确途径吗？或者是否有一些我无法通过 Google 找到的算法，有人知道它已经做到了吗？

Answer 1

您可以从这篇开创性论文开始，然后使用 Google 学者：

及时后退和前进

Bern, Marshall, and David Eppstein. "Quadrilateral meshing by circle packing." International Journal of Computational Geometry & Applications 10.04 (2000): 347-360.

---

         
          ^{Part of Fig.1}

---

特别是，大部分论文都是关于用圆圈包装多边形 实现特定属性，例如，

---

---