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

Question

这是我的第一篇文章,如果我违反任何礼仪规则,请告诉我.

我正在尝试在python中编写一个程序,其中包含形状文件(现在是国会区)并用圆圈"打包"它们.最终目标是获得圆的中心点和半径.我想以最少的圆圈覆盖最大区域.

到目前为止,我通过谷歌找到的所有资源都是关于标准几何对象(如正方形/圆形/三角形等)中的圆形包装......所以我的本能是尝试将这些形状转换为三角形或其他东西,然后应用一些现有的算法更简单的形状.

如果形状有很多小的凹边,这似乎是解决问题的正确途径吗？或者是否有一些我无法通过谷歌找到的算法,任何人都知道这已经做到了？总计算几何noob但愿意学习.

Answer 1

您可以从这篇开创性的论文开始,然后使用Google学术搜索及时向前和向前移动:

伯尔尼,马歇尔和大卫埃普斯坦."通过圆形填料进行四边形网格划分." International Journal of Computational Geometry&Applications 10.04(2000):347-360.

         
          ^{图1的一部分}

特别是,本文的大部分内容都是用圆形包装多边形来实现特定的属性,例如: