求最小矩形覆蓋一組無重疊矩形的算法我有一組矩形，我想“減少”這個集合，所以我有最少的矩形來描述與原始集相同的面積。如果可能的話，我希望它也是快速的，但我更關心的是獲得盡可能低的矩形數量。我現在有了一種方法，它大部分時間都在工作。目前，我從最左上角的矩形開始，看看是否可以在保持矩形的同時，向右和向下擴展它。我這樣做，直到它不能再展開，刪除和拆分所有相交的矩形，并添加擴展矩形回到列表中。然后再用下一個左上角最矩形開始這個過程，以此類推。但在某些情況下，它不起作用。例如：使用這組三個矩形，正確的解決方案將以兩個矩形結束，如下所示：但是，在這種情況下，我的算法從處理藍色矩形開始。這將向下展開并拆分黃色矩形(正確)。但是，當黃色矩形的其余部分被處理時，它不是向下展開，而是先向右擴展，然后取回先前拆分的部分。然后處理最后一個矩形，它不能向右或向下展開，所以原來的矩形集是左。我可以調整算法，先向下擴展，然后再對。這樣可以解決這種情況，但在類似的翻轉場景中也會導致同樣的問題。編輯：為了澄清，原來的一組矩形不重疊，也不需要連接。如果矩形的一個子集是連通的，則完全覆蓋它們的多邊形可以在其上有孔。