最小的包围盒在封装的2D空间中包含一组盒子

Question

我的包装坐标同时具有有限的2D空间（我的意思是左边将环绕到右边缘，同样向上/向下）。

我也有一套框对齐轴。这些框在空间内具有浮动坐标。

问题：找到与包围所有框的轴对齐的最小边界框。边界框CAN被缠绕。

样品：

（粉红色表示空间的界限，红框需要被封闭，蓝色边框表示尽可能小的边框）

Answer 1

A可用于广泛的算法找出最大的垂直间隙，即最远的两条垂直线，它们之间没有框。

类似地，可以使用清扫算法来找出最大的水平间隙。显然，两个间隙都可以包裹边缘。

从2D空间中移除间隙留下的形状是包含所有框的最小边界框。我不确定是否保证所有包含框的最小区域，但是不存在具有小于这个尺寸的尺寸的边界框。如果存在，它将定义两个间隙（垂直水平为&），它们都大于最大值。

可以在O（N * log N）中完成扫描以检测两个间隙，其中N是框的数量。

Answer 2

由边界框包围的总面积的％将是：由边界框=（由水平边界包围水平范围％）*（的垂直范围％封闭总面积的

％的垂直封闭边界）

明显考虑到包装。因此，您可以独立地最小化水平和垂直边界，以尽量减少总面积。

要最小化水平边界，您需要找到一个矩形右边缘和下一个左边缘之间的最大间距。您可以通过将所有边（左和右）排序为单个列表并遍历它，在获得左边时递增计数并在右边递减时递增。您的最大差距是当数值从0 - > 1时x值的最大差异。您必须专门处理环绕式情况，只需通过水平重复矩形一次，即可轻松完成此操作，的总面积。在初始化初始化计数时，您还必须考虑缠绕矩形。

然后对垂直边界也这样做。