计算相交矩形的周长和面积? [英] 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.

推荐答案

可以通过sweep-line算法来完成.

我们将从左到右扫一条假想线.我们会注意到直线和矩形集合之间的交点表示一组间隔的方式，并且当我们遇到矩形的左边缘或右边缘时它会发生变化.

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 之后的交点长度为 L，则该线将扫过的面积等于 (x2 - x1) * L，从 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 为前一个相关的 x 坐标.
   • 设 x2 为当前相关的 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.

左和右是指矩形的边.

这个想法仅用于计算面积，但是，您可以修改它来计算周长.基本上，您会想知道在某个 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 log 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).

您可以在 TopCoder.

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

您可以在 PEG 裁判维基阅读段树的各种使用方法/a>.

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屋！