矩形与矩形相交的面积

Question

下面是 2 个矩形。给定矩形顶点的坐标 - (x1, y1)...(x8, y8)，如何计算重叠区域（下图中白色）的面积？

注意：

1. 点的坐标可以是任意的
2. 矩形可以重叠也可以不重叠
3. 当矩形不重叠或者在点或线处重叠时，假设面积为 0。
4. 如果一个矩形在另一个矩形的内部，则计算较小矩形的面积。

Answer 1

既然你说矩形可能没有对齐，那么可能的答案可能是什么都没有，一个点，一条线段，或者一个有 3-8 条边的多边形。

执行此二维布尔运算的常用方法是选择边缘的逆时针顺序，然后评估关键点（交叉点或角点）之间的边缘段。在每个交叉点，您可以在第一个矩形的边缘段和第二个矩形的边缘之间切换，反之亦然。您始终选择前一段左侧的段。

有很多细节，但基本算法是找到所有交叉点并在其边缘上对它们进行排序适当的数据结构。选择一个交点（如果有）并选择一条远离该交点的线段。找到所选起始线段左侧的另一个矩形的线段。图中，我们选择交叉点a（箭头所指方向）上的绿色线段作为参考线段。右侧另一个矩形的线段是从 a 到 b 的线段。将其用作下一个参考段，然后选择其左侧的绿色段。这是从 b 到 c 的段。以同样的方式查找段cd。下一段是从 d 到角点，因此角点也在相交的顶点列表中。从玉米我们回到a。

要每次选择左侧，请使用相交边的方向向量坐标的确定值。如果有序的有向边对的行列式为正，则说明您的方向正确。

现在您已经有了相交多边形的顶点，您可以使用测量员公式 获取面积。

我留给您的一些细节是：

• 如果一个角与另一个三角形的边或顶点重合怎么办？

• 如果没有交叉点怎么办？ （一个矩形位于另一个矩形内部，或者它们是不相交的 - 您可以使用多边形内的点检查来解决这一问题。请参阅 关于多边形的维基百科文章。

• 如果交点是单个点怎么办？还是线段？

Answer 2

还有另一种方法您可能会觉得有趣，但在这种情况下可能不适用，那就是：

1. 确定最小矩形（其边平行于
   坐标轴 ) 包含两个给定的矩形，让
   将这个新的称为边界框。
2. 选择边界框中的一个随机点，然后检查它是否在两个矩形中，或者
3. 根据需要重复步骤 2（这取决于您想要的结果精度），并有两个计数器，一个用于
   跟踪两个矩形内的点数，并且
   另一个是步骤 2 的重复次数

4. 最终的解决方案是边界框的面积乘以两个矩形内的点数，然后除以数字
   重复步骤 2 的次数，或以公式的形式：

   交集区域 = 边界框区域 * num_of_dots_inside_both /
   num_of_repetitions

当然，重复次数越多，结果就越精确。顺便说一句，这种方法称为蒙特卡罗方法。

Answer 3

您可以通过求解图形所有对边的交点方程来计算交点：
/frac{x - a}{b - a} = /frac{x - c}{d - c}

您以这种方式获得的点可以位于 paralelepide 的侧面，但它们一定不能。您必须检查通过求解方程获得的交点是否位于图形的两侧。如果是这样，您可以计算延伸到两个图形内部的图形边的长度，并通过取它们的倍数来计算交集的平方。

我想我的方法听起来有点过于复杂，但这是我想到的第一个想法。

Answer 4

用三角形而不是矩形来思考问题可能会有所帮助。给定空间中的三个点，求三角形的面积相对简单。

您可以通过将矩形面积减去三角形面积之和来找到相交面积，如下图所示。

本质上它变成了 三角测量问题。

这里有一个很好的介绍，其中包含一些关于数据结构和算法。

编辑：

有一些您可以重用的免费三角测量库。

如果您知道开始时的两个三角形的面积，则可以找到矩形并集的总面积，因此交集将是两个矩形的总面积 - 并集面积。

Answer 5

如果您碰巧使用Qt，那么交集可以计算为QPolygonF交集。
大致如下：

QPolygonF p1,p2, intersected;
p1 << QPointF(r1x1,r1y1) << ... << QPointF(r1x4, r1y4);
p2 << QPointF(r2x1,r2y2) << ... << QPointF(r2x4, r2y4);
intersected = p1.intersected(p2);

float area = polyArea(intersected); // see code block below

（r1 = 矩形 1，r2 = 矩形 2，分别有 4 个 x 和 y 坐标）。

现在计算面积（使用已经提到的鞋带公式）：

inline float polyArea(const QPolygonF& p)
{
    //https://en.wikipedia.org/wiki/Polygon#Area_and_centroid
    const int n = p.size();
    float area = 0.0;
    for (int i=0; i<n; i++)
    {
        area += p[i].x()*p[(i+1)%n].y() - p[(i+1)%n].x()*p[i].y();
    }
    if (area < 0)
        return -0.5*area;
    else
        return 0.5*area;
}

我的代码在这里：公共领域

Answer 6

也许你需要使用opencv。使用 fillPoly() 函数生成一个矩形。确保填充矩形为白色 (255, 255, 255)。然后使用copyTo()函数，您将获得重叠区域。然后检查每个像素的值，如果是白色则+1。