矩形 - 矩形交叉区域

Question

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

注意:

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

Answer 1

由于您声明矩形可能未对齐,因此可能的答案可能是空白,点,线段或具有3-8个边的多边形.

执行此2d boolean操作的常用方法是选择边的逆时针排序,然后评估关键点(交叉点或拐角)之间的边缘段.在每个交叉点,您可以在第一个矩形的边缘段与第二个矩形的边缘之间切换,反之亦然.您始终选择上一段左侧的段.

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

要每次选择左侧,可以使用方向矢量坐标的确定来满足边缘.如果有序有向边对的行列式是正的,那么你就是正确的方法.

现在您已经拥有交叉点多边形的顶点,您可以使用测量员的公式来获取该区域.

我留给你的一些细节是:

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

• 如果没有十字路口怎么办？(一个矩形在另一个内部,或者它们是不相交的 - 你可以使用多边形点检查来解决这个问题.请参阅维基百科关于多边形的文章.

• 如果交叉点是单个点或段,该怎么办？

Answer 2

您可能会发现另一种有趣的方式,但在这种情况下可能不适用,那就是:

1. 确定包含两个给定矩形的最小矩形(其边与坐标轴平行),让我们将新的矩形称为边界框.
2. 选择一个位于边界框中的随机点,并检查它是否在两个矩形中
3. 根据需要重复步骤2(这取决于你想要的结果的精度),并有两个计数器,一个用于跟踪两个矩形内的点数,另一个是数量重复步骤2

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

   intersection_area = bounding_box_area*num_of_dots_inside_both/num_of_repetitions

当然,当重复次数较大时,结果会更精确.顺便说一句,这种方法称为蒙特卡罗方法.