中轴线排列的矩形相交的区域 [英] Area of intersection of axis-aligned rectangles

问题描述

• 每个矩形由4双打是这样的：（X0，Y0，X1，Y1）

• Each rectangle is comprised of 4 doubles like this: (x0,y0,x1,y1)

的边缘平行于X和Y轴

他们被随机放置 - 他们可能接触的边缘，重叠，或没有任何联系。

They are randomly placed - they may be touching at the edges, overlapping , or not have any contact

我需要找到是受它们的重叠形成的区域 - 在画布中的所有区域，不止一个矩形封面（例如使用两个矩形，这将是交点）

I need to find the area that is formed by their overlap - all the area in the canvas that more than one rectangle "covers" (for example with two rectangles, it would be the intersection)

我明白我需要使用扫描线算法。我必须用一个树状结构？什么是使用扫描线算法对于这个问题的最简单的方法是什么？

I understand I need to use sweep line algorithm. Do I have to use a tree structure? What is the easiest way of using sweep line algorithm for this problem?

推荐答案

乍一看，似乎是为O（n ^ 2）的算法应该是简单的，因为我们可以只检查所有成对点。但是，这会产生重复计算的问题，因为这是在3个矩形的所有点会得到数的3倍！意识到后，为O（n ^ 2）算法不看坏我了。如果你能想到一个简单的为O（n ^ 2）算法，请留言。

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.

下面是一个为O​​（n ^ 2日志^ 2 n）的算法。

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

数据结构：点（P）{x_value，isBegin，isEnd，y_low，y_high，rectid}

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

[对于每一个点，我们有一个单一x_value，二y_values​​，和该矩形的ID从该点来到]

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

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

1. Given n rectangles, first create 2n points as above using the x_left and x_right values of the rectangle.

创建点列表，和排序上x_value。这需要为O（n log n）的时间

Create a list of points, and sort it on x_value. This takes O(n log n) time

从左边（索引0），使用地图，当你看到一个开始说，当你看到终点删除启动。

Start from the left (index 0), use a map to put when you see a begin, and remove when you see an end point.

在换句话说：

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轴。

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.

这篇关于中轴线排列的矩形相交的区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！