求最小矩形覆盖一组无重叠矩形的算法

Question

求最小矩形覆盖一组无重叠矩形的算法我有一组矩形，我想“减少”这个集合，所以我有最少的矩形来描述与原始集相同的面积。如果可能的话，我希望它也是快速的，但我更关心的是获得尽可能低的矩形数量。我现在有了一种方法，它大部分时间都在工作。目前，我从最左上角的矩形开始，看看是否可以在保持矩形的同时，向右和向下扩展它。我这样做，直到它不能再展开，删除和拆分所有相交的矩形，并添加扩展矩形回到列表中。然后再用下一个左上角最矩形开始这个过程，以此类推。但在某些情况下，它不起作用。例如：使用这组三个矩形，正确的解决方案将以两个矩形结束，如下所示：但是，在这种情况下，我的算法从处理蓝色矩形开始。这将向下展开并拆分黄色矩形(正确)。但是，当黄色矩形的其余部分被处理时，它不是向下展开，而是先向右扩展，然后取回先前拆分的部分。然后处理最后一个矩形，它不能向右或向下展开，所以原来的矩形集是左。我可以调整算法，先向下扩展，然后再对。这样可以解决这种情况，但在类似的翻转场景中也会导致同样的问题。编辑：为了澄清，原来的一组矩形不重叠，也不需要连接。如果矩形的一个子集是连通的，则完全覆盖它们的多边形可以在其上有孔。