给定n个矩形的坐标，找到k个矩形相交区域的面积是多少？

Question

给定由它们的左下角和右上角坐标[(x1, y1), (x2, y2)]定义的矩形列表[R1，R2，R3]，以及一个值k。

是否有一种最佳方法可以找到k个矩形重叠的区域？

例如：

R1: [(1, 1), (5, 5)]
R2: [(4, 4), (7, 6)]
R3: [(3, 3), (8, 7)]

rectangles = [R1, R2, R3]
k = 2

两个矩形重叠的面积为8。

用蛮力的方法解决这个问题是计算x轴和y轴坐标的最小值和最大值，然后使用它创建一个网格，并在矩形内的每个单元格中递增一个。最后迭代网格以计算具有k值的单元格数以找到解决方案。

该方法的复杂度为O(n^3)，假设每个矩形的大小为n x n，且有n个矩形。

是否有一种运行时间最优的方法来解决这个问题？

- Aditya Bhatia

---

你的复杂度说明有点误导人。实际上，它是O(AT + AU)，其中AT是所有矩形面积之和，而AU是并集（或边界框，具体取决于如何在所有网格单元格上进行最终迭代）的面积。虽然理论上复杂度相同，但实践中可能会通过自动分区kd树更快。也就是说，您不会记录每个网格单元格的重叠部分，而是记录每个树单元格的重叠部分，这些单元格可能会更少，具体取决于矩形大小分布情况。 - Nico Schertler

我会选择“四叉树”。 - 3Dave

Answer 1

通常分析矩形集合的方法是使用扫描线算法。想象一条垂直线从集合左侧开始扫描到右侧。存储当前与该线相交的矩形集合，最初为空。当该线经过任何矩形的垂直边时，需要更新该集合：在每种情况下添加或删除一个矩形。为了使扫描更有效率，使用按垂直线的x坐标排序的列表。

在这种情况下，您还需要一种有效地确定被k个或更多个矩形覆盖的扫描线间隔的方法。这可以通过维护区间树来高效完成。

根据细节，对于n个矩形，效率应该大致为O（n log n），可能还有一个最大重叠深度的附加项。我会让你自己解决细节问题。

- Gene

---

你能详细介绍一下“区间树”部分吗？它是什么，如何构建它？ - DollarAkshay

Answer 2

将矩形按其底部坐标x1排序后插入数据结构中。使用自平衡二叉搜索树等数据结构，时间复杂度为O(N.LogN)，可以在O(N)的时间内遍历整棵树，其中N为矩形数量。例如：

[R1, R3, R2]

在将矩形插入树中的同时，还需保持所有唯一底部和顶部坐标y1和y2的排序列表。在本例中是：

[1, 3, 4, 5, 6, 7]  

现在我们将每个相邻的 y 坐标之间的水平切片视为一维问题（类似于 this answer 中的第一种方法）。

从矩形树的起点开始迭代所有落在此切片中的矩形（记住矩形按y1排序，因此它们在开头分组在一起），并制作一个已排序的唯一x坐标列表，每个值都加1（如果是左坐标）或减1（如果是右坐标）。如果遇到顶部坐标等于切片顶部坐标的矩形，则将其从矩形树中删除，这可以在O(1)内完成。对于示例中的第一个切片，y=1~3，高度为2，如下所示：

[1: +1, 5: -1]  

如果我们对其进行迭代，我们会发现一个宽度为4（因此面积为8）的区域是一个矩形的一部分。

对于示例中的第二个切片，其中y=3~4且高度为1，即：

[1: +1, 3: +1, 5: -1, 8, -1]  

如果我们对其进行迭代，我们会发现一个宽度为2（因此面积为2）的区域是1个矩形的一部分，一个宽度为2（因此面积为2）的区域是2个矩形的一部分，以及一个宽度为3（因此面积为3）的区域是1个矩形的一部分。因此，任何是k个矩形的一部分的区域都会被添加到总数中。等等。

创建矩形树的时间复杂度为O（N.LogN），创建切片列表的时间复杂度为O（N.LogN），迭代切片的时间复杂度为O（N），在每个切片内创建排序后的x坐标列表的时间复杂度为O（N.LogN），因此总时间复杂度为O（N².LogN），与矩形有多大、总面积有多大以及矩形或矩形集群之间有多少重叠无关。

- m69 ''snarky and unwelcoming''