使用段树的矩形并集区域 [英] Area of Union Of Rectangles using Segment Trees

问题描述

我试图了解可用于计算一组轴对齐矩形的并集面积的算法.

我要遵循的解决方案在这里:

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

请注意，我们的基础节点只有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]而不是一个.

所以我们的新细分树将是这样的:

I'm trying to understand the algorithm that can be used to calculate the area of the union of a set of axis aligned rectangles.

The solution that I'm following is here : http://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/

The part I don't understand is :

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.

How do we achieve this in O(n log n) ?

My idea was to create a segment tree, and update each range's value as and when we encounter the range(y range as the height of the rectangle) while line sweeping. And then for for each interval(two consecutive elements in the sorted x array, multiple Δx by the total length of the y range active in this interval, by looking at the sum of all elements in the segment tree)

This would still leads us to having max(y) - min(y) elements in the segment tree's base.

Hence, I'm not sure how this is O(n log n) - where n is the number of rectangles.

Would greatly appreciate any help here.

Thanks!

解决方案

Let's consider some easy case:

According to your understanding you would create segment tree with 11 - 1 = 10 nodes at base, so something like this:

Notice we have only 9 nodes in base, because first node is for interval [1,2], next one for interval [2,3] and so on

And when you enter some rectangle, you would update it's range based on its y coordinates, so after meeting first one on x=0, your segment tree would look like this:

We would also need to use something called lazy propagation to update active intervals on the tree, so all active intervals would contribute 1 to the sum.

So complexity of your current approach is something like O(K log K) where K = max(y)-min(y)

We can easilly reduce this to O(n log n) where n is number of rectangles.

Notice that only important y coordinates are those that exist, so in this example 1,3,6,11

Also notice that there's at most 2*n such coordinates

So we can map all coordinates to some integers so they fit better in segment tree.

This is known as coordinate compression it can be done with something like this:

1. Store all y coordinates in array
2. sort array and remove duplicates
3. use map or hashMap to map original coordinates to it's position in sorted array

So in our example it would be:

1. [1,3,6,11]
2. no duplicates to remove so array still [1,3,6,11]
3. mp[1]=1, mp[3]=2, mp[6]=3, mp[11]=4

So now algorithm stays the same, yet we can use segment tree with only at most 2*n nodes in it's base.

Also we would need to modify our segment tree a little, instead of keeping which y coordinates are on or off we will now keep which intervals of y coordinates are on/off

So we will have nodes for intervals [y0,y1],[y1,y2], ... for all unique sorted values of y.

Also all nodes will contribute y[i]-y[i-1] to the sum (if they are in range and active) instead of one.

So our new segment tree would be something like this:

这篇关于使用段树的矩形并集区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！