algorithm - 找到覆盖所有点的最小面积的两个矩形

Question

给你 n 个点，未排序在一个数组中。您应该找到两个覆盖所有点的矩形，并且它们不应重叠。矩形的边应平行于 x 或 y 坐标。
该程序应返回所有这些点覆盖的最小面积。第一个矩形的面积 + 第二个矩形的面积。

我试图解决这个问题。我按 X 坐标对点进行排序，第一个是第一个矩形的最左边的一个。当我们遍历这些点时，我们会找到最高点和最低点。我在想，当 x 的两个点之间的差异最大时，这意味着第一个点是第一个矩形的最右边，第二个点是第二个矩形的最左边。
当给出第一个示例中的点时，它应该可以工作，但是，如果示例是第二个示例，则它不起作用。因为它会返回这样的东西，这是错误的:

这应该是正确的:

然后我想做两次排序，只是，第二次按 Y 坐标进行排序，然后比较两个总面积。点按 x 排序和点按 y 排序时的面积，较小的面积是正确答案。

Answer 1

这两个矩形不能重叠，因此一个必须完全位于右侧或在另一个之上。您按 x 值对点进行排序并找到最大差距的想法很好，但您应该按照您的建议对两个方向都这样做。这会在您的示例中找到正确的矩形。

然而，最大的差距不一定是理想的 split 点。根据边界框在垂直方向上的范围，拆分可能在其他地方。考虑一个有四个象限的矩形区域，其中两个对角线相对的象限填充有点:

在这里，理想的分割不是最大的差距。

您可以通过考虑具有相邻 x 和 y 坐标的点之间的所有可能分割来找到理想位置。

• 按 x 坐标对点进行排序。
• 按升序扫描排序的数组。通过存储最小和最大 y 坐标来跟踪当前点左侧的最小矩形。为每个点存储这些运行的顶部和底部边界。
• 现在按降序执行相同操作，继续为右侧矩形设置顶部和底部边框。
• 最后，再次遍历这些点并计算左右最小矩形的面积，以便在两个相邻节点之间进行分割。跟踪最小面积总和。

然后对最小的顶部和底部矩形执行相同的操作。可以合并最后两个步骤，这将保存右矩形最小边界的数组。

这在时间上应该是 O(n · log n):排序是 O(n · log n)，单遍是 O(n)。第一个矩形的运行边界框需要 O(n) 额外内存。