当前位置：文江博客话题详情

轴对齐矩形的交集面积

发布于 2024-10-28 01:06:01 字数 255 浏览 2 评论 0原文

每个矩形由 4 个双精度数组成，如下所示：(x0,y0,x1,y1)
边缘平行于 x 轴和 y 轴
它们是随机放置的 - 它们可能在边缘处接触、重叠或没有任何接触

我需要找到由它们重叠形成的区域 - 画布中超过一个矩形“覆盖”的所有区域（例如两个矩形，它将是交集）

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

音盲 2024-11-04 01:06:01

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

这是一个 O(n^2 log^2 n) 算法。

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

[对于每个点，我们有一个 x_value，两个 y_values，以及该点来自的矩形的 ID]

给定n 个矩形，首先使用矩形的 x_left 和 x_right 值创建 2n 个点，如上所述。
创建点列表，并根据 x_value 对其进行排序。这需要 O(n log n) 时间
从左侧（索引 0）开始，当您看到开始时使用地图放置，并在看到结束点时删除。

换句话说：

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 轴感兴趣。

At first blush it seems that an O(n^2) algorithm should be straightforward since we can just check all pairwise points. However, that would create the problem of double counting, as all points that are in 3 rectangles would get counted 3 times! After realizing that, an O(n^2) algorithm doesn't look bad to me now. If you can think of a trivial O(n^2) algorithm, please post.

Here is an O(n^2 log^2 n) algorithm.

Data structure: Point (p) {x_value, isBegin, isEnd, y_low, y_high, rectid}

[For each point, we have a single x_value, two y_values, and the ID of the rectangle which this point came from]

Given n rectangles, first create 2n points as above using the x_left and x_right values of the rectangle.
Create a list of points, and sort it on x_value. This takes O(n log n) time
Start from the left (index 0), use a map to put when you see a begin, and remove when you see an end point.

In other words:

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
    }
}

Next, we need a function that takes a list of rectangles, knowing that the all the rectangles have overlapping x axis, but may or may not overlap on y axis. That is in fact same as this algorithm, we just use a transverse data structures since we are interested in y axis now.

回复收藏 0 原文

~没有更多了~