交叉计算矩形的周长和面积？(Calculate the perimeter and area of

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

我认为，间隔树木可能会有所帮助，但我不知道怎么样。

Answer 1:

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

从左至右，我们将横扫的假想线。我们会发现线和矩形集合的交集代表一组间隔的方式，而且它当我们遇到一个矩形的左侧或右侧边缘的变化。

比方说，在路口不X坐标X1和X2之间变化。然后，如果交点的长度后X1是L，则线将已经横扫等于（X2 - X1）的区域* L，通过扫描从x1到X2。

例如，你可以看看X1与左蓝线，并x1设为以下图片右侧的蓝线（我是从你偷了，并修改了一下:)）：

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

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

insert_interval(y1, y2); 
get_total_length();

那些很容易与段树实现的，所以我就不再赘述了吧。

现在，算法会是这样的：

采取一切垂直细分领域，并通过它们的x坐标进行排序。
对于每一个相关的x坐标（只显示为矩形边缘的那些是很重要的）：
- 令x1是以前的相关x坐标。
- 让X2是当前相关x坐标。
- 设L是由我们的数据结构给出的长度。
- * L总面积总和 - （1×2）添加。
- 删除所有与来自数据结构X = X2段右边缘。
- 加入所有的其中x = X2段数据结构中的左边缘。

通过左右我的意思是一个矩形的边。

给出这个想法只是用于计算面积，但是，你可以修改它来计算周长。基本上，你要知道之前的路口长度之差，它在一些X更改后的坐标。

该算法的复杂度为O（N日志N）的（虽然它取决于你可能获得的输入值的范围，这是很容易处理）。

你可以找到对扫描线算法的广泛主题的更多信息TopCoder公司。

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

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

Answer 2:

以下是O（N 2）的解决方案。

int area = 0;
FOR(triange=0->N)
{
    Area = area trianlges[triangle];
    FOR(int j = triangle+1 -> N)
    {
        area-= inter(triangle , j)
    }
}
return area;

int inter(tri a,tri b)
{
    if ( ( min(a.highY ,b.highY) > max(a.lowerY, b.lowerY) ) && ( min(a.highX ,b.highX) > max(a.lowerX, b.lowerX) ) )
    return ( min(a.highY ,b.highY) - max(a.lowerY, b.lowerY) ) * ( min(a.highX ,b.highX) - max(a.lowerX, b.lowerX) )

    else return 0;
}