Rectangle packing function: Fit small rectangles in one big rectangle

I am looking for a function/script to estimate the maximum number of smaller rectangles - or squares - that may fit into a larger rectangle or square.

The link below is an onlin algoritme that can doe it, as an expample:

https://www.engineeringtoolbox.com/smaller-rectangles-within-larger-rectangle-d_2111.html

[Matt J]

Subject to what constraints?

[Dora de Jong]

@Matt J

Thank you for the response. The Length and Width of the reactangle als input variables.

Larger rectangel A:

A_Width

A_Length

Small rectangels B (to fit in A): The size of the small reactangles are all the same.

B_Width

B_Length

Answer 1

[Nipun]

Hi Dora,

I understand that you want to calculate the number of smaller rectangles that can fit in a given large rectangle using MATLAB. I assume that the smaller rectangles can choose from two possible orientations: horizontal or vertical. In horizontal orientation, the larger edge is lying straight while in the vertical orientation, the larger edge is perpendicular to the base (shorter) edge.

I recommend using Heuristics to calculate the answer. First, I assume that all rectangles have only one fixed orientation; either vertical or horizontal. Then, calculate the maximum number of rectangles that can fit the larger entity.

function maxRectangles = calculateMaxRectanglesWithOrientation(largeWidth, largeHeight, smallWidth, smallHeight)
%calculateMaxRectanglesWithOrientation Calculate max number of smaller rectangles that fit in a larger rectangle with orientation considerations
%   This function calculates the maximum number of smaller rectangles (or squares)
%   that can fit into a larger rectangle, given their dimensions and considering
%   both horizontal and vertical orientations.
%
%   Parameters:
%   largeWidth - Width of the larger rectangle
%   largeHeight - Height of the larger rectangle
%   smallWidth - Width of the smaller rectangle
%   smallHeight - Height of the smaller rectangle
%
%   Returns:
%   maxRectangles - Maximum number of smaller rectangles that can fit with optimal orientation

    % First orientation (width by width, height by height)
    numFitWidth1 = floor(largeWidth / smallWidth);
    numFitHeight1 = floor(largeHeight / smallHeight);
    maxRectangles1 = numFitWidth1 * numFitHeight1;
    
    % Second orientation (width by height, height by width)
    numFitWidth2 = floor(largeWidth / smallHeight);
    numFitHeight2 = floor(largeHeight / smallWidth);
    maxRectangles2 = numFitWidth2 * numFitHeight2;
    
    % Select the maximum of the two orientations
    maxRectangles = max(maxRectangles1, maxRectangles2);
end

This function now calculates the fit for both orientations:

1. The first orientation is the standard one, with the smaller rectangles placed in the same orientation as the larger rectangle.
2. The second orientation rotates the smaller rectangles by 90 degrees.

After calculating the maximum number of smaller rectangles that can fit for both orientations, it selects the maximum of the two.

Then, we fit the rest of the space with the rectangles in a different orientation

function maxRectangles = estimateMixedOrientations(largeWidth, largeHeight, smallWidth, smallHeight)
% Estimate the number of smaller rectangles that can fit into a larger rectangle
% with mixed orientations. This is a heuristic approach and may not find the
% optimal solution.

% Attempt to fit rectangles in one orientation
maxRectangles1 = calculateMaxRectanglesWithOrientation(largeWidth, largeHeight, smallWidth, smallHeight);

% Assuming leftover space is filled with the other orientation, which might not be optimal
% This is a simplistic approach and does not account for the complexities of mixed orientations
remainingWidth = mod(largeWidth, smallWidth);
remainingHeight = mod(largeHeight, smallHeight);
maxRectangles2 = 0;
if remainingWidth > 0
    maxRectangles2 = floor(remainingWidth / smallHeight) * floor(largeHeight / smallWidth);
end
if remainingHeight > 0
    maxRectangles2 = max(maxRectangles2, floor(remainingHeight / smallWidth) * floor(largeWidth / smallHeight));
end

maxRectangles = maxRectangles1 + maxRectangles2;
end

Hope this helps.

Regards,

Nipun