用不同大小的圆包装不规则多边形 [英] Packing an irregular polygon with different sized circles

问题描述

我试图用Shapely用Python编写一个程序，该程序接收形状文件(现在为国会区)，并用圆圈打包".最终目标是获得圆的中心点和半径.我想用最少的圆圈覆盖最大的区域.

I'm trying to write a program in Python with Shapely that takes in shape files (right now congressional districts) and "packs" them with circles. The end goal is to have the center points and radii of the circles. I'd like to cover the maximum area with the least amount of circles.

到目前为止，我在Google上发现的所有资源都是关于在标准几何对象(例如正方形/圆形/三角形等)中进行圆形填充的.所以，我的直觉是尝试将这些形状变成三角形或其他形状，然后应用一些简单的形状的现有算法.

All of the resources I've found via Google so far are about circle packing within standard geometric objects like squares/circles/triangles etc... So my instinct is to try and turn these shapes into triangles or something and then apply some existing algorithm to the simpler shapes.

如果形状具有许多小的凹形边缘，这似乎是解决问题的正确方法吗?还是我无法通过Google找到某种算法，有人已经知道这样做了?

Does this seem like the right path for problem solving if the shapes have lots of small concave edges? Or is there some algorithm I haven't been able to find via Google that anyone knows of that does this already?

推荐答案

您可以从这份开创性的论文开始，然后向后移动&使用Google学术搜索及时转发:

You might start with this seminal paper, and then move backward & forward in time using Google Scholar:

伯恩(Bern)，马歇尔(Marshall)和戴维·埃普斯坦(David Eppstein).通过填方四边形啮合."国际计算几何学杂志应用 10.04(2000):347-360.

---

     
     ^{图1的一部分}

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}

---

尤其是，很多纸都在用圆包装多边形达到特定的特性，例如

---

     

---

In particular, much of the paper is on packing polygons with circles to achieve specific properties, e.g.,

---

         

这篇关于用不同大小的圆包装不规则多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！