我有一个描述我的形状的 2D SDF，但可以将其视为黑白图像（black="inside" white="outside"）。
我想生成一小组覆盖图像的矩形（比如说，其中 8 个），它们可以重叠，并且可以最大限度地减少错误量。错误将是未覆盖的图像的任何剩余“黑色”区域。
图像可能是凸的，有孔的，等等。它是一般的。
我意识到最小的矩形覆盖是 NP 难的，尽管这并不是我所要求的：我要求在给定有限的矩形集的情况下最小化错误。也许这同样困难；不确定。
无论如何，我不需要找到完美的解决方案；体面的启发式方法会很好。
我可以想象一些非常普遍的“贪婪搜索”遍历状态空间，但想知道是否有任何人知道的技巧。
另外：我还看过几篇关于“矩形分解”和“最小解剖”的论文，但这些问题通常假设我想要不相交的矩形。不相交是可以的，但我真的想要最大的覆盖范围，同时允许重叠。
编辑这里是一个例子：
目标图像：
覆盖 4 个矩形（红色、绿色、蓝色、黄色）：
任何未发现的黑色像素都是“错误”。不允许覆盖任何白色像素。
（我不主张任何最优性，或者我已经考虑了每一个细节）
1. 下采样和蛮力：您将黑白地图投影到低分辨率上。在这个较低的分辨率上，您可以用标记左上角和右下角的两个点来表示任何矩形。如果你的分辨率足够低，你可以遍历所有非冗余的点组合，测试它们是否与白色区域重叠（即在封闭的岛屿上），如果没有，那么你可以有效地计算它们的面积。由于您有四个矩形，因此问题的缩放将非常糟糕，但是对于低分辨率，您可能会侥幸成功。
2. 启发式：“生长”矩形：您选择位于黑色区域内的四个位置。对于这些位置中的每一个，您都向外“增长”矩形，直到它们接触到任何白色区域。如果你只在 x 或 y 方向打白色，你可能仍会长成另一个。
您对大量种子点重复上述过程（最好是并行的），然后选出获胜者。你也可以做一些变化，你只选择第一个点，优化相应的最大增长的矩形，然后移动到第二个等等。
3. 投影：你去一个高分辨率的网格，并为每一行和每一列积分，有多少黑白像素。在沿行整合的垂直剖面中，从整合列获得的水平剖面中，您可以轻松确定最大值，这将是开始放置（或增长）矩形的好地方。然后，当您放置第二个时，您会执行相同的过程，但要考虑到您已经用第一个覆盖的区域。您将不得不对极端情况进行一些更正，但这可能会为您节省很多（数字）工作。对于以下我的意思的草图，我提前道歉：
正如我所说，这并不能真正解决您的问题，但可能是构建启发式的起点。