Find Gaps and Overlaps in Rectangular Prisms

Question

Alex 2025-5-14

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2177188-find-gaps-and-overlaps-in-rectangular-prisms

评论： Matt J 2025-5-15

jenga.png

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 %s\n', 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 %s\n', 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 %s\n', 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.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Alex 2025-5-15

编辑：Alex 2025-5-15

在 MATLAB Online 中打开

I define a gap as any location in the box that isn't filled by a prism. If two prisms touch at their edges, like how p1 and p5's x ranges touch, I don't count that as an overlap.

prisms.p1.x = [75 200];
prisms.p5.x = [200 1000];
% No gap or overlap here since p1 ends at 200 and p5 starts at 200. 

Alex 2025-5-15

在 MATLAB Online 中打开

However, if two prisms don't touch, then there is a gap. A prism doesn't have to be touched on every axis to form a gap.

prisms.p1.x = [75 200];
prisms.p5.x = [200 1000];
% No gap here since p1 ends at 200 and p5 starts at 200. 
prisms.p1.x = [75 199];
prisms.p5.x = [200 1000];
% There is a gap here since the values between 199 and 200 aren't filled
% in. 

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2025-5-15

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2177188-find-gaps-and-overlaps-in-rectangular-prisms#answer_1565322

编辑：Matt J 2025-5-15

If you can get R2025a with the PDE Toolbox, you gain access to tools that are very well-suited to this problem. In particular with subtract(),

https://www.mathworks.com/help/pde/ug/fegeometry.subtract.html

and union(),

https://www.mathworks.com/help/pde/ug/fegeometry.union.html

you can subtract the union of cuboids from a solid box, thus exposing the cavities.

2 个评论
显示无隐藏无

Alex 2025-5-15

Oh wow, that's interesting. I was hoping to port this into Python and going down this route might make that very difficult. I'll try this out regardless, as it looks like a great tool.

Matt J 2025-5-15

在 MATLAB Online 中打开

I don't think it should be hard, e.g.,

%MATLAB
function model = buildBricksModel(boxDims, bricks)
% buildBricksModel(boxDims, bricks)
% boxDims = [L, W, H] of the main box
% bricks = struct array with fields: x, y, z, w, h, d
% where (x, y, z) is the corner, and w/h/d are dimensions
model = createpde();
box = multicuboid(boxDims(1), boxDims(2), boxDims(3));
% Convert bricks to geometry objects
brickSolids = [];
for i = 1:length(bricks)
    b = bricks(i);
    % Create and position the brick
    brick = multicuboid(b.w, b.h, b.d);
    brick = translate(brick, [b.x + b.w/2, b.y + b.h/2, b.z + b.d/2]);
    brickSolids = [brickSolids, brick];
end
% Union all bricks
if ~isempty(brickSolids)
    brickUnion = brickSolids(1);
    for i = 2:length(brickSolids)
        brickUnion = union(brickUnion, brickSolids(i));
    end
    gm = subtract(box, brickUnion);
else
    gm = box;
end
% Assign geometry
model.Geometry = gm;
% Optional: generate mesh here
% generateMesh(model);
end

#PYTHON
import matlab.engine
# Start MATLAB engine
eng = matlab.engine.start_matlab()
# Define box dimensions (length, width, height)
box_dims = [100, 100, 100]
# Define list of bricks
brick_data = [
    {"x": 10, "y": 10, "z": 10, "w": 30, "h": 30, "d": 30},
    {"x": 50, "y": 20, "z": 20, "w": 20, "h": 40, "d": 20},
    {"x": 10, "y": 60, "z": 10, "w": 40, "h": 30, "d": 30}
]
# Convert to MATLAB struct array
brick_structs = []
for b in brick_data:
    brick_structs.append(eng.struct(**{
        "x": b["x"], "y": b["y"], "z": b["z"],
        "w": b["w"], "h": b["h"], "d": b["d"]
    }))
brick_matlab_array = matlab.struct([brick_structs])  # wrap as MATLAB struct array
# Call MATLAB function
eng.cd('path/to/your/matlab/scripts')  # Update to correct path
model = eng.buildBricksModel(box_dims, brick_matlab_array, nargout=1)
# Optional: visualize in MATLAB
eng.eval("pdegplot(model, 'FaceAlpha', 0.5, 'FaceLabels', 'on')", nargout=0)

请先登录，再进行评论。

Answer 2

Matt J 2025-5-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2177188-find-gaps-and-overlaps-in-rectangular-prisms#answer_1565294

编辑：Matt J 2025-5-15

在 MATLAB Online 中打开

Does a "gap" not occur whenever the two prisms being compared neither touch, nor overlap? If so, why not as below?

% Fit the following rectangular prisms in a box:
prism(1).x = [75 200];     % Min/max of x range for prism 1
prism(1).y = [4 100];      % Min/max of y range for prism 1
prism(1).z = [1e3 1e4];    % Min/max of z range for prism 1
prism(2).x = [20 80];
prism(2).y = [0.1 2.2];
prism(2).z = [0 1e3];
prism(3).x = [80 115];
prism(3).y = [0.1 4];
prism(3).z = [0 1e3];
prism(4).x = [20 180];
prism(4).y = [2.2 8];
prism(4).z = [0 1e3];
prism(5).x = [200 1000];
prism(5).y = [0 1];
prism(5).z = [0 1e4];
ij=nchoosek(1:5,2);
clear contactType
for k=height(ij):-1:1
    i=ij(k,1);
    j=ij(k,2);
    contactType(k,1)=comparePrisms(prism(i),prism(j));
end
T=table(ij,contactType)
T = 10x2 table
      ij       contactType 
    ______    _____________

    1    2    "unconnected"
    1    3    "touching"   
    1    4    "touching"   
    1    5    "unconnected"
    2    3    "touching"   
    2    4    "touching"   
    2    5    "unconnected"
    3    4    "overlapping"
    3    5    "unconnected"
    4    5    "unconnected"
function contactType=comparePrisms(pa,pb)
   f=@(a,b) any(b(1)<=a & a<=b(2));
   f=@(a,b) f(a,b) | f(b,a);
   Q(1)=f(pa.x,pb.x);
   Q(2)=f(pa.y,pb.y);
   Q(3)=f(pa.z,pb.z);
   f=@(q) numel(unique(q));
   N(1)=f([pa.x,pb.x]);
   N(2)=f([pa.y,pb.y]);
   N(3)=f([pa.z,pb.z]);
   if all(Q) && ~any(N==3)
       contactType="overlapping"; %prisms intersect with positive volume
   elseif all(Q) && any(N==3)
       contactType="touching";    %prisms intersect, but with zero volume
   else
       contactType="unconnected"; %prisms do not intersect
   end
end

12 个评论
显示 10更早的评论隐藏 10更早的评论

Alex 2025-5-15

编辑：Alex 2025-5-15

在 MATLAB Online 中打开

prism_example.png

I tried your code with a different set of prisms (see attached diagram)

% Fit the following rectangular prisms in a box:
prism(1).x = [0 3];     % Min/max of x range for prism 1
prism(1).y = [0 6];     % Min/max of y range for prism 1
prism(1).z = [0 1];     % Min/max of z range for prism 1
prism(2).x = [0 5];
prism(2).y = [6 8];
prism(2).z = [0 1];
prisms(3).x = [5 10];
prisms(3).y = [6 8];
prisms(3).z = [0 1];
prisms(4).x = [3 10];
prisms(4).y = [3 6];
prisms(4).z = [0 1];
prisms(5).x = [3 10];
prisms(5).y = [0 3];
prisms(5).z = [0 1];

And it produced the following output:

T =
  10×2 table
      ij       contactType 
    ______    _____________
  2    "touching"   
  3    "unconnected"
  4    "touching"   
  5    "touching"   
  3    "touching"   
  4    "unconnected"
  5    "touching"   
  4    "unconnected"
  5    "touching"   
  5    "touching"   

The ideal solution here would be for essentially no output at all, as all of the prisms fit perfectly into a box.

Alex 2025-5-15

It's possible - I was also thinking about using a 3D grid of finely spaced points and just seeing if any of them fall in either multiple prisms, or no prisms. I figured I'd go for gold and try something more mathematically-based first.

Alex 2025-5-15

编辑：Alex 2025-5-15

For the record, the initial code that I posted doesn't work with this new set of prisms; it reports too many overlaps.

请先登录，再进行评论。

Find Gaps and Overlaps in Rectangular Prisms

3 个评论
显示 1更早的评论隐藏 1更早的评论

回答（2 个）

2 个评论
显示无隐藏无

12 个评论
显示 10更早的评论隐藏 10更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

Find Gaps and Overlaps in Rectangular Prisms

3 个评论 显示 1更早的评论隐藏 1更早的评论

回答（2 个）

2 个评论 显示 无隐藏 无

12 个评论 显示 10更早的评论隐藏 10更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

3 个评论
显示 1更早的评论隐藏 1更早的评论

2 个评论
显示无隐藏无

12 个评论
显示 10更早的评论隐藏 10更早的评论