algorithm - 包裹二维空间上包含一组框的最小边界框

Question

我有有限的 2D 空间，双向都包含坐标(我的意思是向左走会环绕到右边缘，向上/向下也是如此)。

我还有一组与轴对齐的框。这些盒子在空间内有 float 坐标。

问题:找到与包含所有框的轴对齐的最小边界框。边界框可以环绕。

示例:

(粉色表示空间边界，红色框需要围起来，蓝色边框表示尽可能小的边界框)

Answer 1

扫掠算法可用于找到最大的垂直间隙，即最大距离的两条垂直线，它们之间没有框。

类似地，可以使用扫掠算法来找到最大的水平间隙。显然，两个间隙都可以环绕边缘。

从 2D 空间中去除间隙后留下的形状是包含所有框的最小边界框。我不确定它是否保证具有所有包含框的最小面积，但不存在两个尺寸都小于此尺寸的边界框。如果它存在，它将定义两个大于最大间隙的间隙(垂直和水平)。

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