最小的包圍盒在封裝的2D空間中包含一組盒子

Question

我的包裝座標同時具有有限的2D空間（我的意思是左邊將環繞到右邊緣，同樣向上/向下）。

我也有一套框對齊軸。這些框在空間內具有浮動座標。

問題：找到與包圍所有框的軸對齊的最小邊界框。邊界框CAN被纏繞。

樣品：

（粉紅色表示空間的界限，紅框需要被封閉，藍色邊框表示儘可能小的邊框）

Answer 1

A可用於廣泛的算法找出最大的垂直間隙，即最遠的兩條垂直線，它們之間沒有框。

類似地，可以使用清掃算法來找出最大的水平間隙。顯然，兩個間隙都可以包裹邊緣。

從2D空間中移除間隙留下的形狀是包含所有框的最小邊界框。我不確定是否保證所有包含框的最小區域，但是不存在具有小於這個尺寸的尺寸的邊界框。如果存在，它將定義兩個間隙（垂直水平爲&），它們都大於最大值。

可以在O（N * log N）中完成掃描以檢測兩個間隙，其中N是框的數量。

Answer 2

由邊界框包圍的總面積的％將是：由邊界框=（由水平邊界包圍水平範圍％）*（的垂直範圍％封閉總面積的

％的垂直封閉邊界）

明顯考慮到包裝。因此，您可以獨立地最小化水平和垂直邊界，以儘量減少總面積。

要最小化水平邊界，您需要找到一個矩形右邊緣和下一個左邊緣之間的最大間距。您可以通過將所有邊（左和右）排序爲單個列表並遍歷它，在獲得左邊時遞增計數並在右邊遞減時遞增。您的最大差距是當數值從0 - > 1時x值的最大差異。您必須專門處理環繞式情況，只需通過水平重複矩形一次，即可輕鬆完成此操作，的總面積。在初始化初始化計數時，您還必須考慮纏繞矩形。

然後對垂直邊界也這樣做。