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