3

我正在寻找一种方法来计算单个矩形和一小组矩形的并集之间的交集面积。

我想要的数学表示

我正在使用 Java，所有矩形都用整数 (x,y,w,h) 表示。所有矩形都与 x/y 轴对齐。有什么建议么？

4

4 回答 4

1

遍历并将您的矩形表示为 (x,y,w,h)，而不是 (x1,y1,x2,y2)，即 (x,y,x+w,y+h)。

然后，遍历所有 Rj 并将矩形“剪辑”到 Rect1 的坐标：

Rj.x1 = max(Rj.x1, Rect1.x1)
Rj.y1 = max(Rj.y1, Rect1.y1)
Rj.x2 = min(Rj.x2, Rect1.x2)
Rj.y2 = min(Rj.y2, Rect1.y2)

现在，通过并删除任何 Rj 的地方Rj.x1>=Rj.x2或Rj.y1>=Rj.y2在这种情况下，矩形没有相交。

之后，总结剩余矩形的所有区域（简单(Rj.x2-Rj.x1) * (Rj.y2-Rj.y1)）。

此时，您将重复计算任何被剪裁的 Rj 重叠的区域。

因此，您需要遍历所有 Ri 和所有 Rj，其中 j>i 并且将两者相互夹住，但是这一次，如果存在交叉点（与上述相同的测试），则需要减去与您到目前为止的值相交的区域，以消除重复计算。

不幸的是，这将双重删除三重重叠的任何区域。因此，您将需要找到这些区域并将它们重新添加进去。等等，对于四重重叠、五重重叠等。

听起来会变得很混乱......

也许最简单的方法是将 Rj 绘制到红色画布上，然后在最后计算 Rect1 内的红色像素。（当然，您不必使用真正的 Canvas。您可以使用位数组编写自己的。）甚至可能存在一些场景（例如具有许多小矩形的小坐标空间），这比解析解。但是，当然，这只有在您有整数坐标时才有效。

于 2013-02-11T06:25:35.293 回答
1

您将可能在 Rect1 和 RectSet 联合中的每个矩形之间有一个唯一的交集。因此，您将分别在 Rect1 和联合中的每个矩形之间进行交集。相交区域是 Rect1 和并集中的矩形之间所有相交部分的并集。

优化是为矩形的联合创建一个丰富的矩形（希望在创建联合时完成）。如果 Rect1 不与这个边界矩形相交，你可以跳过做任何进一步的交点和空的区域。

于 2013-02-11T04:31:40.813 回答
1

两个矩形的交集本身就是一个矩形（可能是退化的，但它们的面积为零并且可以忽略）。此外，并集的交集与交集的并集相同（分配律）。因此，您可以将 R1 与每个 Rj 相交并找到结果矩形的并集。

要找到联合，最简单的方法可能是将场景分成垂直条纹，方法是在每个顶点上画一条垂直线。然后在每个条带内，这是一个众所周知的一维问题，通过计算进出点并删除计数大于一的点来解决。

于 2013-02-11T05:48:12.457 回答
0

nm 的答案和PQuinn的答案都建议将交集分布在联合中，然后找到联合的区域。这是个好主意。

在 java 中，我建议在 R1 和 Rj 之间创建一组新的非退化交叉点，基于大多数交叉点将退化的假设。然后使用http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html上的算法来找到交叉点集的面积。

于 2014-05-22T16:50:20.630 回答