Rectangle packing function: Fit small rectangles in one big rectangle

Question

Dora de Jong 2021-3-31

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/789009-rectangle-packing-function-fit-small-rectangles-in-one-big-rectangle

回答： Nipun 2024-5-14

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

2 个评论
显示无隐藏无

Matt J 2021-3-31

Subject to what constraints?

Dora de Jong 2021-3-31

@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 2024-5-14

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/789009-rectangle-packing-function-fit-small-rectangles-in-one-big-rectangle#answer_1456976

在 MATLAB Online 中打开

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:

The first orientation is the standard one, with the smaller rectangles placed in the same orientation as the larger rectangle.
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