计算相交矩形的周长和面积？

Question

我搜索了很多，但是没有找到一个适用于这种情况的好答案。我们有一些水平或垂直的矩形，它们可以随意放置在页面上。它们可以重叠，也可以有共同的边缘，或者彼此分离。我想找到一个O(nlogn)的算法，可以找到这些矩形的周长和面积。这些图片可能会让问题更加清晰。我认为区间树可能会有所帮助，但我不确定如何使用。

- CoderInNetwork

---

我的猜测是周长 :) - gus

我认为你只能得到O(n^2)作为最佳结果，因为你必须检查一个矩形与所有其他矩形之间的交集，然后计算交集的面积和每个矩形的周长，以便不会将其重复添加到总和中。但基本上，你需要先获取所有矩形交点，这样你才知道在计算中下一步要移动到哪里。 - SoluableNonagon

哈哈！是的，有时候在字典中寻找一个好词汇的周长搜索失败了。 :) - CoderInNetwork

Answer 1

这可以通过一种“扫描线”算法完成。

我们将从左到右扫描一条虚拟的直线。我们会注意到直线与矩形集合之间的交集表示一组区间，并且当我们遇到矩形的左侧或右侧边缘时，它会发生变化。

假设交集在x坐标x1和x2之间不会改变。那么，如果交集在x1之后的长度为L，则扫描线从x1到x2扫过的面积将等于（x2 - x1) * L。

例如，您可以将x1看作下图中的左蓝线，将x2看作右蓝线： 很明显，我们的扫描线的交集在这些点之间不会改变。但是，蓝色交集与红色交集非常不同。

我们需要一个具有以下操作的数据结构：

insert_interval(y1, y2); 
get_total_length(); 

那些很容易用线段树实现，所以我现在不会详细介绍。现在，算法将按如下方式进行：1.获取所有垂直线段并按其x坐标排序。2.对于每个相关的x坐标（只有作为矩形边缘出现的坐标才重要）：a.让x1成为前一个相关的x坐标。b.让x2成为当前相关的x坐标。c.让L成为数据结构给出的长度。d.将（x2-x1）* L添加到总面积和中。e.从数据结构中删除所有x = x2的右侧边缘线段。f.将所有x = x2的左侧边缘线段添加到数据结构中。通过“左”和“右”，我是指矩形的两侧。这个想法仅适用于计算面积，但是，您可以修改它以计算周长。基本上，您需要知道在某个x坐标处更改之前和之后的交集长度之间的差异。

算法的复杂度为O(N log N)，尽管它取决于输入值的范围，但这很容易处理。

您可以在TopCoder上找到有关“扫描线”算法的更多信息。

您可以在PEG judge wiki上阅读有关使用“线段树”的各种方法。

这是我（非常古老的）实现该算法作为SPOJ问题NKMARS解决方案的代码：implementation。

- gus

---

非常感谢。这个算法的时间复杂度是多少？我认为它不是O(nlogn)。对吗？ - CoderInNetwork

是的，没错。我已经修改了答案（并添加了我的旧实现的链接）。 - gus

Answer 2

以下是O(N2)的解决方案。

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;
}

- blackmath

---

如果有两个以上的矩形在同一点相交，则该方法无效。 - 2147483647