检查两个盒子是否重叠的算法

Question

我已经理解了关于矩形的算法，但是对于给定x、y、z和高度值的箱子感到困惑。不重叠的条件为：

1. 箱子A在箱子B上方
2. 箱子A在箱子B下方
3. 箱子A在箱子B左侧
4. 箱子A在箱子B右侧

我的理解正确吗？请指导一些遗漏的点。

- Atihska

---

你还需要检查它是在后面还是前面。总共6次检查。 - ariel

x、y、z和高度？所以是四个维度？通常z是高度，或者是x或y。或者只有x、y和z？ - Bernhard Barker

@ariel 谢谢.. 嗯，6个检查。 - Atihska

@Dukeling 通常情况下，z轴代表高度，但我看到过这样的问题，感到困惑。 - Atihska

Answer 1

当且仅当所有轴的投影重叠时，两个沿轴对齐的盒子（任意尺寸）重叠。沿某个轴的投影就是该轴上的坐标范围。

上图中的蓝色盒子和绿色盒子重叠，因为它们在所有轴上的投影都重叠。蓝色盒子和橙色盒子不重叠，因为它们在x轴上的投影不重叠（注意它们在y轴上的投影是重叠的）。绿色盒子和橙色盒子不重叠，因为它们在y轴上的投影不重叠（而它们在x轴上的投影是重叠的）。

因此，当涉及到1D盒子（区间）的代码时，我们有：

box1 = (xmin1, xmax1)
box2 = (xmin2, xmax2)
isOverlapping1D(box1,box2) = xmax1 >= xmin2 and xmax2 >= xmin1

对于2D盒子（矩形），我们有：

box1 = (x:(xmin1,xmax1),y:(ymin1,ymax1))
box2 = (x:(xmin2,xmax2),y:(ymin2,ymax2))
isOverlapping2D(box1,box2) = isOverlapping1D(box1.x, box2.x) and 
                             isOverlapping1D(box1.y, box2.y)

对于3D盒子，我们有：

box1 = (x:(xmin1,xmax1),y:(ymin1,ymax1),z:(zmin1,zmax1))
box2 = (x:(xmin2,xmax2),y:(ymin2,ymax2),z:(zmin2,zmax2))
isOverlapping3D(box1,box2) = isOverlapping1D(box1.x, box2.x) and 
                             isOverlapping1D(box1.y, box2.y) and
                             isOverlapping1D(box1.z, box2.z)

- coproc

---

准备好使用一行代码：isOverlapping = (x1min < x2max AND x2min < x1max AND y1min < y2max AND y2min < y1max)（如果需要，可以添加z，如果您想将“接触”称为重叠，请切换到<=） - brittohalloran

isOverlapping = (x1min < x2max && x2min < x1max && y1min < y2max && y2min < y1max) 的翻译是：如果x1的最小值小于x2的最大值，且x2的最小值小于x1的最大值，同时y1的最小值小于y2的最大值，且y2的最小值小于y1的最大值，则 isOverlapping 为真。 - itzjackyscode

这个线程的问题是：如果xmax1 >= xmin2并且xmax2 >= xmin1，我们是否需要检查其他轴以查看盒子是否相交？我知道我错过了一些显而易见的东西，但有人能给我一个例子吗，在这个例子中两个盒子在x轴上不相交（xmax1 >= xmin2并且xmax2 >= xmin1评估为false），但在y轴或z轴上相交？ - syth3

@jmb7438 上面的橙色框和绿色框在x轴上相交，但在y轴上不相交，因此它们整体上不相交。 - coproc

@coproc 噫。谢谢！哈哈，我知道我漏了一个明显的东西。 - syth3

Answer 2

if(xMin1 <= xMax2 || xMax1 >= xMin2)
 
if(yMin1 <= yMax2 || yMax1 >= yMin2)

if(zMin1 <= zMax2 || zMax1 >= zMin2)

所有这些条件都必须为真，才能使盒子不重叠。

此外，我假设盒子边缘可以位于相同的x、y、z坐标上。

如果不是这样，请去掉等号。

if(xMin1 < xMax2 || xMax1 > xMin2)
 
if(yMin1 < yMax2 || yMax1 > yMin2)

if(zMin1 < zMax2 || zMax1 > zMin2)

- Kay

---

你需要使用AND而不是OR（我将||解读为OR）：isOverlapping = (x1min < x2max AND x2min < x1max AND y1min < y2max AND y2min < y1max)。 - brittohalloran

Answer 3

这可以通过检查两个范围是否不相交来解决，即两个范围是不相交的。

如果A的最大X小于B的最小X，则它们不可能相交。

如果A的最小X大于B的最大X，则它们不可能相交。

如果A的最大Y小于B的最小Y，则它们不可能相交。

如果A的最小Y大于B的最大Y，则它们不可能相交。

A = [xmin,ymin,xmax,ymax]
B = [xmin,ymin,xmax,ymax]

// True if intersecting
!(A[0] > B[2] || A[2] < B[0] || A[1] > B[3] || A[3] < B[1])

- Dennis Bauszus