我在2D空间中有一组矩形和任意形状。形状不一定是多边形（可以是圆形），并且矩形具有不同的宽度和高度。任务是用尽可能接近的矩形近似形状。我无法更改矩形尺寸，但可以旋转。
听起来很像包装问题和覆盖问题，但覆盖区域不是矩形的…
我想这是NP问题，而且我很确定应该有一些论文能够显示出很好的启发式解决方案，但是我不知道该怎么办？我应该从哪里开始？
更新： 我刚刚想到一个主意，但我不确定是否值得研究。如果我们将边界形状视为充满水的物理模具，该怎么办？每个矩形均被视为具有大小的带正电的粒子。现在将最小的矩形放到它上面。然后在大小上随机将下一个按大小放下。如果矩形太近，它们会互相排斥。继续添加矩形，直到使用完所有矩形。这种方法行得通吗？
我认为您可以寻找打包和自动布局生成算法。自动VLSI布局生成算法可能需要类似的内容，就像纺织品布局问题一样。
本文Hegedüs：用矩形覆盖多边形的算法似乎解决了类似的问题。而且由于这篇论文是1982年的，所以看一下引用该论文的论文可能会很有趣。此外，本次会议似乎正在讨论与此相关的研究问题，因此可能是进行此想法研究的关键字或名称的起点。
我不知道计算几何学研究是否有针对您特定问题的算法，或者这些算法是否足够容易/实用。如果必须这样做而又无法查找以前的工作，这就是我将如何处理它。这只是一个方向，到目前为止还不是一个解决方案…
将其表述为优化问题。您具有选择哪个矩形（是或否）的离散变量和连续变量（三角形的位置和方向）的离散变量。现在，您可以设置两个独立的优化程序：拾取矩形的离散优化程序；一旦指定了矩形，便会连续优化位置和方向。交织这两个优化。当然，困难在于优化的制定和设计错误能量，以使其不会陷入某些奇怪的配置（局部最小值）中。我将尝试解决连续最小二乘问题，以便可以使用标准的优化库。
