查找包含空間中所有點的最大空矩形的集合

Question

給定一個由（白色）矩形和一組佔據該空間的（黑色）矩形限制的二維空間，我正在尋找以某種方式將空白色）空間。爲此，我想創建一組（白色）矩形，使得對於空間中的任何給定點（點不屬於任何「黑色」矩形），最大的空矩形存在於所產生的一組白色矩形中。

謝謝

Answer 1

http://rd.springer.com/chapter/10.1007%2F3-540-53487-3_50 本文描述了一個有效的方法來解決我的問題。

問候， 戴姆詹·

Answer 2

你在一個網格（即圖像）或在一個連續的二維空間？我的答案是針對每個點都有整數座標的情況。在另一種情況下，你可以用我的答案獲得近似值。

如果我理解正確的話你的問題，你需要兩樣東西：

1. 所有最大的空矩形（即人口只有白點的矩形的列表，至極不能在任何方向，而不包括擴展一個黑點）（在文獻中也稱爲「最大空矩形」或MER）。
2. 矩形指針的二維數組，它指示每個點包含該點的最大空白矩形。其他數據結構也是可能的，但我不會描述它們，因爲選擇主要取決於您的目標應用程序要求。

爲了計算列表，可以使用算法O（N），其中N是黑白圖像中像素的數量。你可以在http://www.ulg.ac.be/telecom/rectangles找到一篇描述這種算法的論文，附帶一些（未優化的）C++源代碼。實際上，它非常快。

爲了計算pinters的二維數組，您需要遍歷所有最大的空矩形的列表，併爲每個矩形遍歷所有包含的像素的指針（如果需要）。由於最多有N個最大的空矩形（對於prrof，請參閱鏈接在http://www.ulg.ac.be/telecom/rectangles上的紙張），並且每個矩形包含最多N個像素，此步驟在最壞情況下爲O（N^2）。我不知道是否有可能降低這一步驟的成本。