使用段树的矩形联合区域

Question

我试图理解可用于计算一组轴对齐矩形的并集区域的算法。

我关注的解决方案是：http://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/

我不明白的部分是：

段树是此数据结构的正确选择。它具有更新操作的复杂度O（logn）和查询的O（1）。我们需要使用每个节点的分数来扩充分段树，具有以下属性。

• 每个节点对应于y-间隔，该y-间隔是节点范围内所有索引上的基本y间隔的并集。
• 如果节点值为零，则分数是后代分数的总和（如果节点是叶子，则为0）。
• 如果节点值为正，则得分是对应于节点的y间隔的长度。

我们如何在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坐标的哪些间隔打开/关闭

因此，对于y的所有唯一排序值，我们将具有间隔[y0，y1]，[y1，y2]，...的节点。

此外，所有节点都将y [i] -y [i-1]贡献给总和（如果它们在范围和活动中）而不是一个。

所以我们的新分段树将是这样的：

Answer 2

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

考虑每个矩形，您将更新二进制段树中的范围[x，y]。基本上发生的是，你是

• 搜索x作为树中的左边界（log（N）时间）
• 搜索y作为树中的右边界（log（N）时间）

假设您为x找到的节点是[x，a]，并且它具有[z，a]的父节点，并且此父节点具有兄弟[a，b]。显然，如果y不在[a，b]之下，则覆盖[a，b]的整个范围，因此您在[a，b]子树下增加此节点而不是所有单个段节点。

结果，搜索/更新过程看起来像这样。

• 如果父节点[a，c]有两个子节点[a，b]，[b，c]并且左边界x在[a，b]中，则决定是否在节点[b，c]中增加值（取决于y是否大于c）
• 如果父节点[a，c]有两个子节点[a，b]，[b，c]并且右边界y在[b，c]中，则决定是否在节点[a，b]中增加值（取决于x是否小于a）

基本上，在潜入一个节点之前，决定是否更新其兄弟。

您决定是否更新的节点数是log（N）（对于x）+ log（N）（对于y）。