c++ - 长方形-长方形相交面积

Question

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

请注意:

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

Answer 1

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

执行此2d boolean 操作的常用方法是选择边缘的逆时针顺序，然后评估临界点(交叉点或拐角)之间的边缘段。在每个交叉点，您在第一个矩形的边缘段和第二个矩形的边缘之间切换，反之亦然。您总是选择前一个片段左侧的片段。

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

要每次选择左侧，请使用相交边的方向 vector 坐标的确定值。如果有序有向边对的行列式是正的，那么你就走对了。

现在您已经有了交集多边形的顶点，您可以使用 surveyor's formula获取该区域。

我要留给你的一些细节是:

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

• 如果没有路口怎么办？ (一个矩形在另一个矩形之内，或者它们不相交——您可以使用多边形中的点检查来解决这个问题。参见 Wikipedia article on polygons。

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