algorithm - 轴对齐矩形的交集区域

Question

• 每个矩形由 4 个 double 组成，如下所示:(x0,y0,x1,y1)

• 边平行于x轴和y轴

• 它们是随机放置的——它们可能在边缘接触、重叠或没有任何接触

我需要找到由它们重叠形成的区域 - Canvas 中超过一个矩形“覆盖”的所有区域(例如，有两个矩形，它就是交集)

我知道我需要使用扫描线算法。我必须使用树结构吗？使用扫描线算法解决此问题的最简单方法是什么？

Answer 1

乍一看，复杂度为 O(n^2) 的算法似乎应该很简单，因为我们只需检查所有成对的点。然而，这会产生重复计算的问题，因为 3 个矩形中的所有点都会被计算 3 次!在意识到这一点之后，O(n^2) 算法现在对我来说并不坏。如果您能想到简单的 O(n^2) 算法，请发帖。

这是一个复杂度为 O(n^2 log^2 n) 的算法。

数据结构:点(p){x_value, isBegin, isEnd, y_low, y_high, rectid}

[对于每个点，我们有一个 x_value、两个 y_value 和这个点来自的矩形的 ID]

1. 给定 n 个矩形，首先使用矩形的 x_left 和 x_right 值创建 2n 个点。

2. 创建一个点列表，并根据 x_value 对其进行排序。这需要 O(n log n) 时间

3. 从左边(索引 0)开始，看到开始时使用 map 放置，看到结束点时删除。

换句话说:

Map m = new HashMap();  // rectangles overlapping in x-axis
for (Point p in the sorted list) {
    if (p.isBegin()) {
        m.put(p);  // m is keyed off of rectangle id
        if (s.size() >= 2) {
            checkOverlappingRectangles(m.values())
        }
    } else {
        m.remove(p);  // So, this takes O(log n) time
    }
}

接下来，我们需要一个接受矩形列表的函数，知道所有矩形都有重叠的 x 轴，但在 y 轴上可能重叠也可能不重叠。这实际上与该算法相同，我们只是使用横向数据结构，因为我们现在对 y 轴感兴趣。