Solved Checking if two cuboids intersect

I was wondering if there was a better way of checking if two cuboids intersect other than checking each and every single block in each of the two cuboids. Thanks in advance.

 

Chew the best way to do it is to use the worldedit api. their methods would be most efficient. you can do so much with that api, its amazing look at the source code

 

Edit: wrong

 

Necrodoom there's ways to boxes can intersect with none of the corners are inside of the other one, otherwise I would have done it that way.

 

Maybe you need to take location (1 and 2) and see if x1-x2 = 1 or y1 = y2 = 1 or z1-z1 = 1.

After that you make a abs (to be positive) or

Code:java

sx = x1-x2;
If (x < 0){
s = s * (-1)
}
 

 

Sorry, but that's a mathematical impossibility. Two cuboids intersect if (and only if) at least one corner of cuboid A is inside cuboid B.

Strike that, see what Skye wrote below.

 

It's an easy and interesting mathematical problem.

ResultStatic No it's not the best and most efficient way, because you need an api, an own efficient solution is much better

Necrodoom You are right.

An example:
You have the cuboids A and B with the coordinates:
Amin(xAmin, yAmin, zAmin)
Amax(xAmax, yAmax, zAmax)

Bmin(xBmin, yBmin, zBmin)
Bmax(xBmax, yBmax, zBmax)

Amin and Bmin are the edges of the cube with the lowest coordinates.
Amax and Bmax with the highest.

You now have to check if xAmin or xAmax is between xBmin and xBmax, and the same for y and z. If the result is true for x, y, and z, the cuboids intersect.

But, as you already mentioned there are other cases, which you cant find out with this method (for example if the cuboid B is in cuboid A).

For this case you have to do the same again, but you have to exchange A and B.

if-statement:

Code:java

if ((xAmin >= xBmin && xAmin < xBmax || xAmax >= xBmin && xAmax < xBmax) && (same with y) && (same with z) || (xBmin >= xAmin && xBmin < xAmax || xBmax >= xAmin && xBmax < xAmax) && (same with y) && (same with z)) {//code}

 

Two rectangles can overlap without any corners being inside the other, though.

Code:

     XXXXX
   YYOOOOOYY
   YYOOOOOYY
     XXXXX

What one would have to check for is if any of the edges of a cuboid falls within another, which can be done with coordinates from the corners.

 

Yeah, you're quite right; apologies Chew.

 

hmmm ok, I see, then my method wold not work in this case. I will think about it again

 

Just check whether the lowest or highest X-, Y- and/or Z-coordinate of both cuboids lie between (or are equal to) the ones of the other cuboid.

 

I've never needed to do such a check in an efficient manner, so I've always done it the easy, inefficient way, but I think something like this would work:

Code:

if ((xAMin >= xBMin && xAMin <= xBMax) || (xAMax >= xBMin && xAMax <= xBMax)
  || (yAMin >= yBMin && yAMin <= yBMax) || (yAMax >= yBMin && yAMax <= yBMax)
  || (zAMin >= zBMin && zAMin <= zBMax) || (zAMax >= zBMin && zAMax <= zBMax))
      return true;

I'm on a tablet so I can't test it, but it's some horribly long logic like that (but definitely more efficient). There should be some good examples on Stack Overflow, though.

Edit: But since Minecraft is in blocks, you'll want to use >= and <=

 

Skye would return true for 2 cuboids side by side.

 

Skye I didn't check your code completely, but you don't consider the exactly that case, where I had my problem.

I have already a solution for the whole problem, I will post it later, because i am at work now (no time now).

We just have 2 different cases to consider:
1st: cuboid A contains cuboid B or contrariwise
2nd: when you imagine the cuboid with lines and surfaces between the edges, the cuboids intersect, if a line penetrates a surface of the other cuboid

if one of these cases is true, the cuboids intersect.

(sry for my bad english)

I will figure out a code for this when I am at home

EDIT by Moderator: merged posts, please use the edit button instead of double posting.

 

stonar96 I think it would work fine if you put it in a method and do a check like

Code:

if (hasOverlap(Location a, Location b) || hasOverlap(Location b, Location a)) {}

Sorry for the jumps in logic, but it's really hard to type on this lol

 

Skye yes, but this was already my idea, look at my first post, but this method would not work in some cases, as you said, because this method assumes, that a corner is inside the other cube

stonar96 stonar96

... and this is my new idea.

I will code it when I am at home from work.

EDIT by Moderator: merged posts, please use the edit button instead of double posting.

 

The code my mind came up with:

Code:java

public boolean intersectsCuboid(Cuboid a, Cuboid b)
{
    if(!intersectsDimension(a.getXMin(), a.getXMax(), b.getXMin(), b.getXMax()))
        return false;
 
    if(!intersectsDimension(a.getYMin(), a.getYMax(), b.getYMin(), b.getYMax()))
        return false;
 
    if(!intersectsDimension(a.getZMin(), a.getZMax(), b.getZMin(), b.getZMax()))
        return false;
 
    return true;
}
 
public boolean intersectsDimension(int aMin, int aMax, int bMin, int bMax)
{
    return aMin <= bMax && aMax >= bMin;
}

The basic idea is to check, if the 2 cuboids intersect in all used dimensions.
(aMin <= aMax && bMin <= bMax) has to be true.
Also, it returns true for cuboids side by side. This is on purpose, as these cuboids share points.
(Especially when you consider that it's MC, and one X is a Block)

I checked it on paper and it did work, however I don't gurantee it.

 

Syd Sry, but no. I think your code also only consider the "edge-in-the-other-cuboid-cases", or if I interpret it right the whole cube has to be in the other one.

I thought about it again, I now have a solution in my brain. I will write it down now, but its really not that easy.

 

stonar96
No, it should work if the cube is only partly within the other. (And also if no edge is within a cube but they still intersect)

I only inspect one dimension at a time to find out if there is actually a point of this cube what mets with the other cube on this axis. If thats not the case, they'll never meet in 3D space.

This obviously only works, when everything has any angle of x*90° to the axis.


PS: for efficiency I recommend to check the Y-Axis as the last one, as this is more likely to return true than X and Z within MC

 

Syd yes you are right, it should work I tried all variations on one axis. Perfect solution, after my first try I thought this would be way more difficult, your solution seemed too simple for me. Sry. Good work!

 

pretty much every server already has worldedit anyway, and you have much more capability with the api.

 

ResultStatic actually some of my commands conflict with WorldEdit, so that's not an option.

 

Just use:

if (x1 + width1 > x2 && x1 < x2 + width2
&& same with y/height && same with z/length)
retun true;
else
return false;

 

Skye
I believe that would also return true for any cuboids not even close to each other in the x or z plane if they had equivalent ymin and ymax values.
EDIT: I think you meant to use && instead of || in two parts... I could be mistaken.