Find Gaps and Overlaps in Rectangular Prisms

I have rectangular prisms at fixed locations defined below, and I’m trying to see if they fit in a box without any gaps or overlaps. The perfect no-gaps, no-overlaps solution looks like the picture of the attached Jenga tower.
% Fit the following rectangular prisms in a box:
prisms.p1.x = [75 200]; % Min/max of x range for prism p1
prisms.p1.y = [4 100]; % Min/max of y range for prism p1
prisms.p1.z = [1e3 1e4]; % Min/max of z range for prism p1

prisms.p2.x = [20 80];
prisms.p2.y = [0.1 2.2];
prisms.p2.z = [0 1e3];

prisms.p3.x = [80 115];
prisms.p3.y = [0.1 4];
prisms.p3.z = [0 1e3];

prisms.p4.x = [20 180];
prisms.p4.y = [2.2 8];
prisms.p4.z = [0 1e3];

prisms.p5.x = [200 1000];
prisms.p5.y = [0 1];
prisms.p5.z = [0 1e4];

% The box that the prisms must fit in, given the values above, is:
box.x = [20 1000]; % Min/max of x range for the box of prisms
box.y = [0 100]; % Min/max of x range for the box of prisms
box.z = [0 1e4]; % Min/max of x range for the box of prisms
Above is a struct called prisms. It has 5 fields; each field describes one prism (p1,p2,p3,p4,p5) using x,y,z coordinates. I want to identify if the rectangular prisms have any overlaps or gaps between them, and if so, report where those gaps and/or overlaps occur. The ranges are all aligned with the axes, and are always >=0.
The size of the box that the prisms must fit in is defined to be the min and max values over all prisms for a particular axis. If two prisms touch at only one point in their range, I don’t count that as an "overlap". I don’t want to move the prisms, but instead want to report where two prisms overlap, or where there are gaps in the box.
I’ve found all the overlapping regions by testing pairs of rectangular prisms for overlap, and it seems to work:
%% Get all combinations of classes (combinations since order does not matter)
nFields = length(fieldnames(prisms));
combos = nchoosek(1:nFields,2);
nCombos = nchoosek(nFields,2);

% Index the struct by index instead of field name
fns = fieldnames(prisms);

%% Check for overlap between each pair of classes
for ic = 1:nCombos
x11 = prisms.(fns{combos(ic,1)}).x(1);
x12 = prisms.(fns{combos(ic,1)}).x(2);
y11 = prisms.(fns{combos(ic,1)}).y(1);
y12 = prisms.(fns{combos(ic,1)}).y(2);
z11 = prisms.(fns{combos(ic,1)}).z(1);
z12 = prisms.(fns{combos(ic,1)}).z(2);

x21 = prisms.(fns{combos(ic,2)}).x(1);
x22 = prisms.(fns{combos(ic,2)}).x(2);
y21 = prisms.(fns{combos(ic,2)}).y(1);
y22 = prisms.(fns{combos(ic,2)}).y(2);
z21 = prisms.(fns{combos(ic,2)}).z(1);
z22 = prisms.(fns{combos(ic,2)}).z(2);

if( (x12>x21 && y12>y21 && z12>z21) || (x21>x12 && y21>y12 && z21>z12) )
% There is either overlap, or the edge of classes align

% Check for overlap in x
if( ((x12>=x21) && (x11<=x22)) || ((x11<=x22) && (x21<=x21)) )
if((x21==x12) || (x11==x22))
continue;
else
fprintf(‘Overlap in x between %s and %sn’, fns{combos(ic,1)}, fns{combos(ic,2)});
fprintf(‘ Limits for %s x: [%g %g]n’, fns{combos(ic,1)}, x11, x12);
fprintf(‘ Limits for %s x: [%g %g]n’, fns{combos(ic,2)}, x21, x22);
end
end

% Check for overlap in y
if( ((y12>=y21) && (y11<=y22)) || ((y11<=y22) && (y21<=y21)) )
if((y21==y12) || (y11==y22))
continue;
else
fprintf(‘Overlap in y between %s and %sn’, fns{combos(ic,1)}, fns{combos(ic,2)});
fprintf(‘ Limits for %s y: [%g %g]n’, fns{combos(ic,1)}, y11, y12);
fprintf(‘ Limits for %s y: [%g %g]n’, fns{combos(ic,2)}, y21, y22);
end
end

% Check for overlap in z
if( ((z12>=z21) && (z11<=z22)) || ((z11<=z22) && (z21<=z21)) )
if((z21==z12) || (z11==z22))
continue;
else
fprintf(‘Overlap in z between %s and %sn’, fns{combos(ic,1)}, fns{combos(ic,2)});
fprintf(‘ Limits for %s z: [%g %g]n’, fns{combos(ic,1)}, z11, z12);
fprintf(‘ Limits for %s z: [%g %g]n’, fns{combos(ic,2)}, z21, z22);
end
end
end
end
I just can’t get the last part which will identify where the gaps happen. I think I can modify the above code to push this function across the finish line, but I need some help.I have rectangular prisms at fixed locations defined below, and I’m trying to see if they fit in a box without any gaps or overlaps. The perfect no-gaps, no-overlaps solution looks like the picture of the attached Jenga tower.
% Fit the following rectangular prisms in a box:
prisms.p1.x = [75 200]; % Min/max of x range for prism p1
prisms.p1.y = [4 100]; % Min/max of y range for prism p1
prisms.p1.z = [1e3 1e4]; % Min/max of z range for prism p1

prisms.p2.x = [20 80];
prisms.p2.y = [0.1 2.2];
prisms.p2.z = [0 1e3];

prisms.p3.x = [80 115];
prisms.p3.y = [0.1 4];
prisms.p3.z = [0 1e3];

prisms.p4.x = [20 180];
prisms.p4.y = [2.2 8];
prisms.p4.z = [0 1e3];

prisms.p5.x = [200 1000];
prisms.p5.y = [0 1];
prisms.p5.z = [0 1e4];

% Index the struct by index instead of field name
fns = fieldnames(prisms);

if( (x12>x21 && y12>y21 && z12>z21) || (x21>x12 && y21>y12 && z21>z12) )
% There is either overlap, or the edge of classes align

% Check for overlap in z
if( ((z12>=z21) && (z11<=z22)) || ((z11<=z22) && (z21<=z21)) )
if((z21==z12) || (z11==z22))
continue;
else
fprintf(‘Overlap in z between %s and %sn’, fns{combos(ic,1)}, fns{combos(ic,2)});
fprintf(‘ Limits for %s z: [%g %g]n’, fns{combos(ic,1)}, z11, z12);
fprintf(‘ Limits for %s z: [%g %g]n’, fns{combos(ic,2)}, z21, z22);
end
end
end
end
I just can’t get the last part which will identify where the gaps happen. I think I can modify the above code to push this function across the finish line, but I need some help. I have rectangular prisms at fixed locations defined below, and I’m trying to see if they fit in a box without any gaps or overlaps. The perfect no-gaps, no-overlaps solution looks like the picture of the attached Jenga tower.
% Fit the following rectangular prisms in a box:
prisms.p1.x = [75 200]; % Min/max of x range for prism p1
prisms.p1.y = [4 100]; % Min/max of y range for prism p1
prisms.p1.z = [1e3 1e4]; % Min/max of z range for prism p1

prisms.p2.x = [20 80];
prisms.p2.y = [0.1 2.2];
prisms.p2.z = [0 1e3];

prisms.p3.x = [80 115];
prisms.p3.y = [0.1 4];
prisms.p3.z = [0 1e3];

prisms.p4.x = [20 180];
prisms.p4.y = [2.2 8];
prisms.p4.z = [0 1e3];

prisms.p5.x = [200 1000];
prisms.p5.y = [0 1];
prisms.p5.z = [0 1e4];

% Index the struct by index instead of field name
fns = fieldnames(prisms);

if( (x12>x21 && y12>y21 && z12>z21) || (x21>x12 && y21>y12 && z21>z12) )
% There is either overlap, or the edge of classes align

Cart

Cart