包裹二维 space 上包含一组框的最小边界框
Smallest bounding box enclosing set of box on wraped 2D space
我有有限的 2D space，双向坐标都被环绕（我的意思是向左走会环绕到右边缘，up/down 也是如此）。
我还有一组与轴对齐的框。这些框在 space.
内有浮动坐标
问题：找到与包含所有框的轴对齐的最小边界框。边界框可以环绕。
样本：
（粉红色表示space边界，红色框需要被包围，蓝色边框表示尽可能小的边界框）
可以使用扫描算法找到最大的垂直间隙，即最远的两条垂直线，它们之间没有框。
类似地，可以使用扫掠算法来找到最大的水平间隙。显然，两个间隙都可以环绕边缘。
从 2D space 中移除间隙留下的形状是包含所有框的最小边界框。我不确定它是否保证具有所有包含框的最小 area，但不存在 both 尺寸小于这个。如果它存在，它将定义两个间隙（垂直和水平）都大于最大间隙。
可以在 O(N * log N) 中完成扫描以检测两个间隙，其中 N 是框的数量。
边界框所包围的总面积的百分比将为：
边界框包围的总面积的百分比 =（水平边界包围的水平范围的百分比）*（垂直边界包围的垂直范围的百分比）
显然考虑到了换行。因此，您可以独立地最小化水平和垂直边界，以最小化总面积。
要最小化水平边界，您需要找到一个矩形的右边缘与下一个矩形的左边缘之间的最大间隙。您可以通过将所有边缘（左和右）排序到一个列表中并遍历它，在获得左侧时递增计数并在获得右侧时递减来有效地执行此操作。当计数从 0 -> 1 时，您最大的差距是 x 值的最大差异。您必须特别处理 wrap-around 情况，只需水平重复一次矩形即可轻松做到这一点，偏移量总面积的宽度。在开始时初始化计数时，您还必须考虑 wrapped-around 个矩形。
然后对垂直边界执行同样的操作。
我有有限的 2D space，双向坐标都被环绕（我的意思是向左走会环绕到右边缘，up/down 也是如此）。
我还有一组与轴对齐的框。这些框在 space.
内有浮动坐标问题：找到与包含所有框的轴对齐的最小边界框。边界框可以环绕。
样本：
（粉红色表示space边界，红色框需要被包围，蓝色边框表示尽可能小的边界框）
可以使用扫描算法找到最大的垂直间隙，即最远的两条垂直线，它们之间没有框。
类似地，可以使用扫掠算法来找到最大的水平间隙。显然，两个间隙都可以环绕边缘。
从 2D space 中移除间隙留下的形状是包含所有框的最小边界框。我不确定它是否保证具有所有包含框的最小 area，但不存在 both 尺寸小于这个。如果它存在，它将定义两个间隙（垂直和水平）都大于最大间隙。
可以在 O(N * log N) 中完成扫描以检测两个间隙，其中 N 是框的数量。
边界框所包围的总面积的百分比将为：
边界框包围的总面积的百分比 =（水平边界包围的水平范围的百分比）*（垂直边界包围的垂直范围的百分比）
显然考虑到了换行。因此，您可以独立地最小化水平和垂直边界，以最小化总面积。
要最小化水平边界，您需要找到一个矩形的右边缘与下一个矩形的左边缘之间的最大间隙。您可以通过将所有边缘（左和右）排序到一个列表中并遍历它，在获得左侧时递增计数并在获得右侧时递减来有效地执行此操作。当计数从 0 -> 1 时，您最大的差距是 x 值的最大差异。您必须特别处理 wrap-around 情况，只需水平重复一次矩形即可轻松做到这一点，偏移量总面积的宽度。在开始时初始化计数时，您还必须考虑 wrapped-around 个矩形。
然后对垂直边界执行同样的操作。