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

Question

我进行了很多搜索，但没有找到适合这种情况的好答案。我们有一些水平或垂直的矩形。它们可以随机放置在页面上。它们可以重叠或具有共同的边缘或彼此分开。我想找到一个 O(nlogn) 的算法，可以找到这些矩形的周长和面积。这些图片可能会让问题变得清晰。

我认为区间树可能会有所帮助，但我不确定如何。

Answer 1

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

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

假设 x 坐标x1和x2之间的交点没有变化。然后，如果x1之后的交点长度为L ，则该线将从x1扫到x2 ，扫过一个等于 ( x2 - x1 ) * L的区域。

例如，您可以将x1视为左蓝线，将x1视为下图中的右蓝线（我从您那里偷来并稍作修改 :)）：

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

我们需要一个包含这些操作的数据结构：

insert_interval(y1, y2); 
get_total_length(); 

这些很容易用段树实现，所以我现在不会详细介绍。

现在，算法将如下所示：

1. 获取所有垂直线段并按它们的 x 坐标对它们进行排序。
2. 对于每个相关的 x 坐标（只有那些显示为矩形边缘的坐标很重要）：
   • 令 x1 为先前的相关 x 坐标。
   • 令 x2 为当前相关的 x 坐标。
   • 让 L 是我们的数据结构给出的长度。
   • 将 (x2 - x1) * L 添加到总面积总和。
   • 从数据结构中删除所有具有 x = x2 段的右边缘。
   • 将所有具有 x = x2 段的左边缘添加到数据结构中。

左右是指矩形的边。

这个想法仅用于计算面积，但是，您可以修改它来计算周长。基本上，您会想知道交点在某个 x 坐标处变化前后的长度之间的差异。

该算法的复杂度为 O(N log N)（尽管它取决于您可能作为输入获得的值的范围，但这很容易处理）。

您可以在TopCoder上找到有关扫描线算法这一广泛主题的更多信息。

您可以在PEG 评委 wiki上阅读有关使用分段树的各种方法。

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

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