我在二维空间中有一组矩形和任意形状。形状不一定是多边形（可能是圆形），矩形有不同的宽度和高度。任务是用尽可能接近的矩形来近似形状。我无法更改矩形尺寸，但允许旋转。
这听起来与包装问题和覆盖问题非常相似，但覆盖区域不是矩形......
我想这是 NP 问题，我很确定应该有一些论文显示出很好的启发式方法来解决它，但我不知道要谷歌什么？我应该从哪里开始？
更新：我刚想到一个想法，但我不确定它是否值得研究。如果我们将边界形状视为充满水的物理模具会怎样。每个矩形被认为是一个带正电的粒子，具有大小。现在将最小的矩形放到它上面。然后在随机点按大小删除下一个。如果矩形太靠近，它们会相互排斥。继续添加矩形，直到全部用完。这种方法可行吗？
我认为您可以寻找打包和自动布局生成算法。自动 VLSI 布局生成算法可能需要类似的东西，就像纺织品布局问题......
这篇论文Hegedüs：Algorithms for Covering Polygons by rectangles似乎解决了类似的问题。由于这篇论文是 1982 年的，所以看看引用这篇论文的论文可能会很有趣。此外，本次会议似乎正在讨论与此相关的研究问题，因此可能是研究此想法的关键字或名称的起点。
我不知道计算几何研究是否有针对您的特定问题的算法，或者这些算法是否足够容易/实用以实现。如果我不得不这样做而无法查找以前的工作，这就是我将如何处理它。这只是一个方向，到目前为止还不是解决方案......
将其表述为优化问题。您有选择哪些矩形的离散变量（是或否）和连续变量（三角形的位置和方向）。现在您可以设置两个独立的优化：选择矩形的离散优化；和一个连续的，一旦给出矩形，就可以优化位置和方向。交错这两个优化。当然，困难在于优化的制定，以及设计你的误差能量，使其不会陷入一些奇怪的配置（局部最小值）。我会尝试将连续作为最小二乘问题，以便我可以使用标准优化库。
我认为这个问题适合用遗传算法和/或进化策略算法来解决。我在某种进化策略算法的帮助下完成了类似的盒子包装问题。在我的博客中查看。
因此，如果您将使用这种方法 - 编码到染色体框中：
然后尝试最小化这样的适应度函数——
y = w1 * box_intersection_area + w2 * box_area_out_of_shape + w3 * average_circle_radius_in_free_space
选择权重 w1,w2,w3 以影响因素的重要性。当遗传算法将找到部分解决方案 - 删除仍然重叠在一起或变形的盒子 - 你将至少有合法（但不是必要的最佳）解决方案。
祝这个有趣的问题好运！
它确实是 NP 难，而且由于它具有高科技应用，因此即使在专利中也没有合理有效的近似策略，更不用说发表的论文了。
在有限的预算下，你能做的最好的事情就是从限制问题开始。假设所有矩形都完全相同，假设所有作为标准矩形的二进制细分的矩形也是允许的，因为您可以有效地预先打包它们以适应您的核心划分。对于额外的点，您还可以形成几个固定模式，用于粘合核心矩形以覆盖一些具有显着不同比例的较大形状。假设您可以更改标准矩形/单元格的尺寸，只要其余部分（预包装和粘合模式）保持不变 - 这为您提供了参数来根据您给出的矩形确定核心矩形的近似大小。
现在您可以使用纵横比来近似这种有限系统可以保证的错误。对于第一次迭代，假设使用简单的细分模式可以有 50% 的错误，然后更改模式以减少错误，但不会增加预打包的渐近复杂度。在一天结束时，您总是只是将给定的矩形分配给您预先计算且现在固定的网格和二进制细分 - 这意味着您根本不尝试进行布局或回溯 - 您总是对第一个近似值感到满意适合网格。
努力定义与您的架构很好地打包的矩形类 - 这再次保持整个过程颠倒 - 你永远不会试图真正适应你所得到的 - 你正在定义你必须得到什么才能很好地完成它 -然后您将其余部分视为错误，因为它是近似值。
然后你可以尝试做更多，但不多——任何滑入回溯或确定任意小错误，这是指数级的。
如果您在研究机构并且可以获得一些超级计算机时间 - 在那里运行一组带有病态混合的详尽搜索，以查看最佳包装的外观，并查看您是否可以导出更多细分模式和/或矩形集的类。
对于头 2 年或研究来说，这应该足够了 :-)