计算相交矩形的周长与面积？ [英] Calculate the perimeter and area of intersecting rectangles?

问题描述

我搜索了很多，但我没有找到一个很好的答案适用于这种情况。 我们有一些矩形是水平或垂直。它们可以随机放置在页面上。它们可以重叠或具有一个公共边缘或分开彼此。 我想找到一个算法O（nlogn），可以找到周边这些矩形和地区。 这些照片可能使问题清晰。

I searched a lot, but I didn't find a good answer that works for this case. We have some rectangles that are horizontal or vertical. They can be placed on the page randomly. They can overlap or have a common edge or be separate from each other. I want to find an algorithm with O(nlogn) that can find perimeter and area of these rectangles. These pictures may make the problem clear.

我觉得区间树木可能会有所帮助，但我不知道怎么样。

I think that interval trees might help, but I'm not sure how.

推荐答案

它可以通过的扫线完成的算法。

我们要扫的假想线从左至右。 我们会发现一路上行和组矩形之​​间的交叉重复presents一组区间，而当我们遇到一个矩形的左侧或右侧边缘它的变化。

We'll sweep an imaginary line from left to right. We'll notice the way the intersection between the line and the set of rectangles represents a set of intervals, and that it changes when we encounter a left or right edge of a rectangle.

假设路口没有不是X坐标的变化 X1 和 X2 。 然后，如果路口后的 X1 是→的长度，该行会风靡的面积等于（ X2 - X1 ）* →，由扫 X1 为 X2

Let's say that the intersection doesn't change between x coordinates x1 and x2. Then, if the length of the intersection after x1 was L, the line would have swept an area equal to (x2 - x1) * L, by sweeping from x1 to x2.

例如，你可以看看 X1 作为左蓝线，和 X1 作为右蓝线以下图片（我是从你偷和修改一点点 ：））：

For example, you can look at x1 as the left blue line, and x1 as the right blue line on the following picture (that I stole from you and modified a bit :)):

有应该清楚的是我们的扫描线的交叉点的不这些点之间变化。然而，蓝色路口是红色的有很大不同。

It should be clear that the intersection of our sweep-line doesn't change between those points. However, the blue intersection is quite different from the red one.

我们需要用这些操作的数据结构：

We'll need a data structure with these operations:

insert_interval(y1, y2); 
get_total_length(); 

这些都是很容易与实施的段树的，所以我就不再赘述了吧。

Those are easily implemented with a segment tree, so I won't go into details now.

现在，该算法会是这样的：

Now, the algorithm would go like this:

1. 采取一切垂直细分领域，并通过它们的X坐标进行排序。
2. 对于每一个相关的x坐标（只有那些表现为矩形的边缘是很重要的）：
   • 让X1是previous相关的x坐标。
   • 让X2 BE现行有关x坐标。
   • 设L是由我们的数据结构中给出的长度。
   • 添加（X2 - X1）。* L总面积之和
   • 删除所有的右键的与数据结构X = X2段边缘。
   • 添加所有的离开的与X = X2段的数据结构的边缘。

1. Take all the vertical segments and sort them by their x coordinates.
2. For each relevant x coordinate (only the ones appearing as edges of rectangles are important):
   • Let x1 be the previous relevant x coordinate.
   • Let x2 be the current relevant x coordinate.
   • Let L be the length given by our data structure.
   • Add (x2 - x1) * L to the total area sum.
   • Remove all the right edges with x = x2 segments from the data structure.
   • Add all the left edges with x = x2 segments to the data structure.

到离开和右键的我的意思是一个矩形的边。

By left and right I mean the sides of a rectangle.

这想法只给出了计算区域，但是，你可以修改它来计算周长。基本上，你要知道这个路口的长度之间的差异之前和之后，在有些X的变化坐标。

This idea was given only for computing the area, however, you may modify it to compute the perimeter. Basically you'll want to know the difference between the lengths of the intersection before and after it changes at some x coordinate.

该算法的复杂度为O（N日志N）（尽管这取决于值的范围内，你可能会得到作为输入，这是很容易处理的）。

The complexity of the algorithm is O(N log N) (although it depends on the range of values you might get as input, this is easily dealt with).

您可以找到对的扫描行的算法，在<一个广泛主题的更多信息href="http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=lineSweep">Top$c$cr.

You can find more information on the broad topic of sweep-line algorithms on TopCoder.

您可以阅读使用的段树的上 PEG法官维基的各种方式。

You can read about various ways to use the segment tree on the PEG judge wiki.

下面是我的（真的老了）执行算法解决的 SPOJ问题NKMARS ：的实施。

Here's my (really old) implementation of the algorithm as a solution to the SPOJ problem NKMARS: implementation.

这篇关于计算相交矩形的周长与面积？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！