algorithm - 用给定的一组矩形填充任意二维形状

Question

我在二维空间中有一组矩形和任意形状。形状不一定是多边形(可以是圆形)，矩形具有不同的宽度和高度。任务是用尽可能接近的矩形来近似形状。我无法更改矩形尺寸，但允许旋转。

听起来很像packing problem和覆盖问题但覆盖区域不是矩形...

我想这是 NP 问题，我很确定应该有一些论文展示了很好的启发式方法来解决它，但我不知道用谷歌搜索什么？我应该从哪里开始？

更新:我刚刚想到一个想法，但我不确定它是否值得研究。如果我们将边界形状视为装满水的物理模具会怎样。每个矩形被认为是具有大小的带正电的粒子。现在将最小的矩形放到它上面。然后在随机点按大小放置下一个。如果矩形太近，它们会相互排斥。继续添加矩形，直到使用完所有矩形。这个方法行得通吗？

Answer 1

我认为您可以寻找打包和自动布局生成算法。自动 VLSI 布局生成算法可能需要类似的东西，就像纺织布局问题......

本文Hegedüs: Algorithms for covering polygons by rectangles似乎解决了类似的问题。由于这篇论文发表于 1982 年，因此查看 papers which cite this one 可能会很有趣.此外，this meeting似乎在讨论与此相关的研究问题，因此可能是从事此想法研究的关键字或名称的起点。

我不知道计算几何研究是否有针对您的特定问题的算法，或者这些算法是否足够容易/实用以实现。如果我不得不在无法查找以前的工作的情况下这样做，我将如何处理它。这只是一个方向，目前还不是解决方案......

将其表述为优化问题。您有选择矩形的离散变量(是或否)和连续变量(三角形的位置和方向)。现在您可以设置两个独立的优化:一个选择矩形的离散优化；和一个连续的，一旦给定矩形就优化位置和方向。交错这两个优化。当然，困难在于优化的制定，以及设计你的错误能量，使其不会陷入一些奇怪的配置(局部最小值)。我会尝试将连续作为 least squares我可以使用标准优化库的问题。