algorithm - 使用线段树的矩形并集面积

Question

我正在尝试了解可用于计算一组轴对齐矩形的并集面积的算法。

我遵循的解决方案在这里:http://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/

我不明白的部分是:

The segment tree is the right choice for this data structure. It has complexity O(logn) for the update operations and O(1) for the query. We need to augment the segment tree with a score per node, with the following properties.

• every node corresponds to a y-interval being the union of the elementary y-intervals over all the indices in the span of the node.
• if the node value is zero, the score is the sum of the scores of the descendants (or 0 if the node is a leaf).
• if the node value is positive, the score is the length of the y-interval corresponding to the node.

我们如何在 O(n log n) 中实现这一目标？

我的想法是创建一个线段树，并在扫线时遇到范围(y 范围为矩形的高度)时更新每个范围的值。然后对于每个区间(排序后的 x 数组中的两个连续元素，通过查看线段树中所有元素的总和，将 Δx 乘以该区间中活跃的 y 范围的总长度)

这仍然会导致我们在线段树的基础中有 max(y) - min(y) 个元素。

因此，我不确定这是 O(n log n) - 其中 n 是矩形的数量。

非常感谢此处的任何帮助。

谢谢!

Answer 1

让我们考虑一些简单的情况:

根据您的理解，您将在基础上创建具有 11 - 1 = 10 个节点的线段树，因此如下所示:

注意我们在 base 中只有 9 个节点，因为第一个节点用于区间 [1,2]，下一个用于区间 [2,3] 等等

当您输入某个矩形时，您会根据它的 y 坐标更新它的范围，因此在 x=0 上遇到第一个矩形后，您的线段树将如下所示:

我们还需要使用一种叫做惰性传播的东西来更新树上的事件间隔，因此所有事件间隔都会对总和贡献 1。

因此，您当前方法的复杂性类似于 O(K log K)，其中 K = max(y)-min(y)

我们可以轻松地将其减少到 O(n log n)，其中 n 是矩形的数量。

请注意，只有重要的 y 坐标是存在的，因此在本例中为 1,3,6,11

还要注意最多有 2*n 个这样的坐标

因此我们可以将所有坐标映射到一些整数，以便它们更好地适合线段树。

这被称为坐标压缩，它可以通过这样的方式完成:

1. 将所有y坐标存储在数组中
2. 排序数组并删除重复项
3. 使用 map 或 hashMap 将原始坐标映射到它在排序数组中的位置

因此在我们的示例中它将是:

1. [1,3,6,11]
2. 没有要删除的重复项，所以数组仍然是 [1,3,6,11]
3. mp[1]=1, mp[3]=2, mp[6]=3, mp[11]=4

所以现在算法保持不变，但我们可以使用其基础中最多只有 2*n 个节点的线段树。

我们还需要稍微修改一下线段树，我们现在将保持 y 坐标的间隔开/关，而不是保持 y 坐标打开或关闭

所以我们将有间隔 [y0,y1],[y1,y2], ... 的节点，用于所有唯一的排序值 y。

此外，所有节点都将为总和贡献 y[i]-y[i-1](如果它们在范围内且处于事件状态)而不是一个。

所以我们的新线段树应该是这样的: