Algorithm to check if two boxes overlap

问题:

I have understood the algorithm in case of rectangles but I am confused with the boxes with x, y, z and height as value given. The conditions for not overlapping are 1) Box A above Box B 2) Box A below Box B 3) Box A left of Box B 4) Box A right of Box B

Am I correct? Please guide some missing points.

回答1:

Two axes aligned boxes (of any dimension) overlap if and only if the projections to all axes overlap. The projection to an axis is simply the coordinate range for that axis.

The blue and the green boxes in the image above overlap because their projections to both axes overlap. The blue and the orange box do not overlap, because their projections to the x-axis do not overlap (note that their projections to the y-axis do overlap). The green and the orange box do not overlap, because their projections to the y-axis don't overlap (while their projections to the x-axis do overlap).

So when it comes to code for 1D boxes (intervals) we have:

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

For 2D boxes (rectangles) we have:

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)

For 3D boxes we have:

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)

回答2:

if(xMin1 <= xMax2 || xMax1 >= xMin1)

if(yMin1 <= yMax2 || yMax1 >= yMin1)

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

All of these conditions have to be true for the boxes to not be overlapped.

Also I assumed that the box edges could lay on the same x,y,z co-ordinates.

If not, just take the equal signs outs.

if(xMin1 < xMax2 || xMax1 > xMin2)

if(yMin1 < yMax2 || yMax1 > yMin2)

if(zMin1 < zMax2 || zMax1 > zMin2)