什么是找到重叠的两个区域的总面积的有效算法 [英] What is an efficient algorithm to find total area of two region which is overlapped

问题描述

我的情况



输入：一组矩形

每个矩形由4个双打组成这个：（x0，y0，w，h）

它们不会在任何角度旋转，它们都是正常的矩形，向上/向下和向左/向右对屏幕的尊重

它们是随机放置的 - 它们可能在边缘接触，重叠，或者没有任何接触

我将有几百个矩形

这是用C实现的



我需要找



区域A和B的联合如果重叠



示例



下面的图片包含两个矩形：A，B

A和B重叠

我要找的是两个地区的总面积

<峰; br /> 
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA<峰; br /> 
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA<峰; br /> 
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA<峰; br / > 
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA<峰; br /> 
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA<峰; br /> 
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA<峰; br /> 
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA<峰; br /> 
 AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB<峰; br /> 
 AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB<峰; br /> 
 AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB<峰; br /> 
 AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB<峰; br /> 
 AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB<峰; br /> 
将峰; br /> 

解决方案

我喜欢这个问题，这是非常有趣的纯粹算法问题，而不是很多编程。但你应该是解决方案的作者，它看起来像一个家庭作业。因此，让我们这样做：我虽然只是一点点，并得出了一个非常有趣的简单想法。我会和你分享这个想法，你会尝试继续。



这是它的样子：你的解释和图片引发了解决这个问题的想法问题首先：对于一对给定的矩形，计算交叉区域（或者可以是零或不是）并从矩形区域的总和中减去该区域。但是泛化不仅会引起问题，而且从一开始就看起来非常低效：对的数量增长为N ² ，其中，假设N是给定矩形的数量。



这是我的想法：



首先，只考虑矩形的左右两侧。在两侧绘制无限垂直直线。您将获得2 * N条垂直线，将整个2D空间分成2 * N + 1个垂直条带（最左侧和最右侧的条带是半无限的，不与任何矩形相交）。除了那些半无限条，我们得到2 * N - 1个垂直条。



同样，考虑到矩形的顶部和底部，我们可以打破整个空间分为2 * N - 1个水平条。两组条带将使由这些无限垂直和水平直线组成的单元格的（2 * N-1） ² 矩阵构建为所有矩形的所有垂直和水平边的延续。为什么这个矩阵对我们非常有用？与初始矩形不同，这些单元格不相交！



现在，您可以快速计算此矩阵的总数。现在，您的问题减少到排序这些单元格。这些单元中的一些包含一个或多个矩形的物质，其他单元是空的。您需要找出空单元格并从矩阵区域中减去它们的区域。这个问题比你最初的问题容易得多。



实际上，我把初始问题简化为一个非常简单的问题，任何人都可以轻松解决。

-SA

您好，



看看在这里的例子和讨论中：

http://stackoverflow.com/questions/244452/what-is-an-efficient-algorithm-to-find-area-of-overlapping-rectangles [ ^ ]



希望这有帮助!! ：）

My situation

Input: a set of rectangles
each rect is comprised of 4 doubles like this: (x0,y0,w,h)
they are not "rotated" at any angle, all they are "normal" rectangles that go "up/down" and "left/right" with respect to the screen
they are randomly placed - they may be touching at the edges, overlapping , or not have any contact
I will have several hundred rectangles
this is implemented in C

I need to find

union of area A and B if overlapped

Example

The image below contains two rectangles: A,B
A and B overlap
What I am looking for is the total area of two region

<br />
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA <br />
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA <br />
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA <br />
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA <br />
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA <br />
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA <br />
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA <br />
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB<br />
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB <br />
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB <br />
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB <br />
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB<br />
                             <br />

解决方案

I like the problem, it is pretty funny purely algorithmic problem, not very much of programming. But you are supposed to be the author of the solution, which looks like a home assignment. Therefore, let's do this: I though just a bit at it and came to a pretty interesting simple idea. I'll share this idea with you, and you will try to continue.

Here is how it looks: your explanation and the pictures provokes the idea to solve the trivial problem first: for a pair of given rectangles, calculate the area of intersection (or can be zero or not) and subtract this area from the sum of rectangle's areas. But generalization not only cause problems, but looks very inefficient from the very beginning: the number of pairs grows as N², where, let's say, N is the number of given rectangles.

Here is my idea:

First, consider just the left and right sides of rectangle. Draw infinite vertical straight lines where the sides are. You will get 2*N vertical lines which break the whole 2D space into 2*N + 1 vertical strips (leftmost and rightmost ones being semi-infinite, not intersecting with any of the rectangles). Excluding those semi-infinite strips, we get 2*N - 1 vertical strips.

Same way, considering top and bottom sides of out rectangles, we can break the whole space into 2*N - 1 horizontal strips. Both sets of strips will make the (2*N - 1)² matrix of cells composed by these infinite vertical and horizontal straight lines build as continuations of all vertical and horizontal sides of all rectangles. Why this matrix is very useful to us? Those cells, unlike the initial rectangles, don't intersect!

Now, you can quickly calculate the total are of this matrix. Now, your problem is reduced to sorting those cells. Some of those cells "contain" the "matter" of one or more rectangles, others are "empty". You need to find out empty cells and subtract their areas from the area of the matrix. This problem is much easier than your initial problem.

Actually, I reduced initial problem to a very trivial one which anyone can easily solve.

—SA

Hi,

Have a look at the examples and the discussion going here:
http://stackoverflow.com/questions/244452/what-is-an-efficient-algorithm-to-find-area-of-overlapping-rectangles[^]

Hope this helps !! :)

这篇关于什么是找到重叠的两个区域的总面积的有效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！