Calculate resizing factor for N small rectangles inside a large rectangle to cover maximum areaMaximum area of a rectangle inside a triangleFind the area of shaded triangle inside of a rectangle.Calculate the width and height of a rectangle, given its diagonal and areaMaximum area of a rectangleHow to divide a large rectangle into N smaller rectanglesOrthogonal lines on Mercator projection?Formula for area of circle sector inside rectangleMaximum angle of triangle inside a rectangleArea inside a rectangleMaximum Area of inscribed rectangle
How to move the player while also allowing forces to affect it
Is it wise to focus on putting odd beats on left when playing double bass drums?
What happens when a metallic dragon and a chromatic dragon mate?
Information to fellow intern about hiring?
Is there a familial term for apples and pears?
Extreme, but not acceptable situation and I can't start the work tomorrow morning
What do the Banks children have against barley water?
LWC and complex parameters
What does "enim et" mean?
Is it legal to have the "// (c) 2019 John Smith" header in all files when there are hundreds of contributors?
Ideas for 3rd eye abilities
How can I fix this gap between bookcases I made?
Prime joint compound before latex paint?
How can I add custom success page
What does it exactly mean if a random variable follows a distribution
When blogging recipes, how can I support both readers who want the narrative/journey and ones who want the printer-friendly recipe?
COUNT(*) or MAX(id) - which is faster?
Domain expired, GoDaddy holds it and is asking more money
What is it called when one voice type sings a 'solo'?
Is domain driven design an anti-SQL pattern?
Can I find out the caloric content of bread by dehydrating it?
What does 'script /dev/null' do?
What causes the sudden spool-up sound from an F-16 when enabling afterburner?
Is there a way to make member function NOT callable from constructor?
Calculate resizing factor for N small rectangles inside a large rectangle to cover maximum area
Maximum area of a rectangle inside a triangleFind the area of shaded triangle inside of a rectangle.Calculate the width and height of a rectangle, given its diagonal and areaMaximum area of a rectangleHow to divide a large rectangle into N smaller rectanglesOrthogonal lines on Mercator projection?Formula for area of circle sector inside rectangleMaximum angle of triangle inside a rectangleArea inside a rectangleMaximum Area of inscribed rectangle
$begingroup$
I have a variable number of small rectangles which are natively 39 x 83 (width by length).
I will also have an arbitrary sized, container rectangle that I need to fit all of the smaller rectangles into. I can resize the small rectangles but I must preserve their aspect ratio and they must all be the same size as each other.
The goal is to resize them such that I cover the maximum possible area of the container rectangle. The small rectangles can not overlap each other or extend outside of the container rectangle.
I feel like this should be a straightforward problem well within my capability of solving - but after struggling with it for 2 days, consulting with my grade 9 son and performing a couple of dozen Google searches, I’m ready to ask for help.
What is the correct way to approach this problem?
linear-algebra rectangles
asked Mar 30 at 3:48
JimJim
1
$endgroup$
add a comment |
$begingroup$
I have a variable number of small rectangles which are natively 39 x 83 (width by length).
I will also have an arbitrary sized, container rectangle that I need to fit all of the smaller rectangles into. I can resize the small rectangles but I must preserve their aspect ratio and they must all be the same size as each other.
The goal is to resize them such that I cover the maximum possible area of the container rectangle. The small rectangles can not overlap each other or extend outside of the container rectangle.
I feel like this should be a straightforward problem well within my capability of solving - but after struggling with it for 2 days, consulting with my grade 9 son and performing a couple of dozen Google searches, I’m ready to ask for help.
What is the correct way to approach this problem?
linear-algebra rectangles
asked Mar 30 at 3:48
JimJim
1
$endgroup$
add a comment |
$begingroup$
I have a variable number of small rectangles which are natively 39 x 83 (width by length).
I will also have an arbitrary sized, container rectangle that I need to fit all of the smaller rectangles into. I can resize the small rectangles but I must preserve their aspect ratio and they must all be the same size as each other.
The goal is to resize them such that I cover the maximum possible area of the container rectangle. The small rectangles can not overlap each other or extend outside of the container rectangle.
I feel like this should be a straightforward problem well within my capability of solving - but after struggling with it for 2 days, consulting with my grade 9 son and performing a couple of dozen Google searches, I’m ready to ask for help.
What is the correct way to approach this problem?
linear-algebra rectangles
asked Mar 30 at 3:48
JimJim
1
$endgroup$
I have a variable number of small rectangles which are natively 39 x 83 (width by length).
I will also have an arbitrary sized, container rectangle that I need to fit all of the smaller rectangles into. I can resize the small rectangles but I must preserve their aspect ratio and they must all be the same size as each other.
The goal is to resize them such that I cover the maximum possible area of the container rectangle. The small rectangles can not overlap each other or extend outside of the container rectangle.
I feel like this should be a straightforward problem well within my capability of solving - but after struggling with it for 2 days, consulting with my grade 9 son and performing a couple of dozen Google searches, I’m ready to ask for help.
What is the correct way to approach this problem?
linear-algebra rectangles
linear-algebra rectangles
asked Mar 30 at 3:48
JimJim
1
asked Mar 30 at 3:48
JimJim
1
asked Mar 30 at 3:48
JimJim
1
asked Mar 30 at 3:48
JimJim
1
asked Mar 30 at 3:48
JimJim
1
1
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I will assume all the small rectangles have to have the same orientation. It is already hard and I give a thought if this is not true at the end. Let the bounding rectangle be $W times H$. We are trying to choose a scale factor $s$ for the $39 times 83$ rectangles that is as large as possible so that we can fit $N$ scaled rectangles in the bounding one.
Assuming the small rectangles have to have the same orientation means the optimum tiling is rectangular. We just have to choose the orientation of the small rectangles and the number that fit across the width.
As a first cut, assume the small rectangles are oriented with the long axis horizontal. They are then $83s$ wide and $39s$ tall, so we get $lfloor frac W83s rfloor$ rectangles horizontally and $lfloor frac H39srfloor$ vertically. We need $lfloor frac W83s rfloorlfloor frac H39srfloorge N$ for the proper number to fit. We start by ignoring the floor signs, so we can find $s=sqrtfrac WH83cdot 39 N$. This just expresses the fact that the small rectangles have to have less area than the large one, ignoring any problems about whether they fit.
At this point you will only succeed if $frac W83s$ and $frac H39s$ are integers, so the outer rectangle is completely filled. You are lucky-declare victory! If not, you have an approximation $n=frac W83s$ to the number of small rectangles you want horizontally. If you place $m$ rectangles horizontally, you need $k=lceil frac Nm rceil$ rows. You can compute the scale factors in each direction as $frac W83m$ and $frac H39k$. Take the lower of these. Now search for the best $m$, which will be near the $n$ we computed above, based on finding the largest scale factor.
Repeat the process for the other orientation of the small rectangles, exchanging $39$ and $83$ and you have the answer under these restrictions.
If you don't insist that the small rectangles have the same orientation, you have one more degree of freedom. You can split $N$ into $N=K+M$ and have $K$ small rectangles in vertical orientation and $M$ in horizontal orientation. You want either the heights or the widths of the two rectangles to be close, but there is more searching to do.
answered Mar 30 at 4:28
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
Thanks very much for the detailed answer. I’ll try to absorb it in the morning - but to answer your question the width must be the short length (portrait orientation) and it may not be rotated. From a quick read of your answer, it seems that the problem was more difficult than I anticipated. Now I feel a little less stupid!
$endgroup$
– Jim
Mar 30 at 6:29
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3167913%2fcalculate-resizing-factor-for-n-small-rectangles-inside-a-large-rectangle-to-cov%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I will assume all the small rectangles have to have the same orientation. It is already hard and I give a thought if this is not true at the end. Let the bounding rectangle be $W times H$. We are trying to choose a scale factor $s$ for the $39 times 83$ rectangles that is as large as possible so that we can fit $N$ scaled rectangles in the bounding one.
Assuming the small rectangles have to have the same orientation means the optimum tiling is rectangular. We just have to choose the orientation of the small rectangles and the number that fit across the width.
As a first cut, assume the small rectangles are oriented with the long axis horizontal. They are then $83s$ wide and $39s$ tall, so we get $lfloor frac W83s rfloor$ rectangles horizontally and $lfloor frac H39srfloor$ vertically. We need $lfloor frac W83s rfloorlfloor frac H39srfloorge N$ for the proper number to fit. We start by ignoring the floor signs, so we can find $s=sqrtfrac WH83cdot 39 N$. This just expresses the fact that the small rectangles have to have less area than the large one, ignoring any problems about whether they fit.
At this point you will only succeed if $frac W83s$ and $frac H39s$ are integers, so the outer rectangle is completely filled. You are lucky-declare victory! If not, you have an approximation $n=frac W83s$ to the number of small rectangles you want horizontally. If you place $m$ rectangles horizontally, you need $k=lceil frac Nm rceil$ rows. You can compute the scale factors in each direction as $frac W83m$ and $frac H39k$. Take the lower of these. Now search for the best $m$, which will be near the $n$ we computed above, based on finding the largest scale factor.
Repeat the process for the other orientation of the small rectangles, exchanging $39$ and $83$ and you have the answer under these restrictions.
If you don't insist that the small rectangles have the same orientation, you have one more degree of freedom. You can split $N$ into $N=K+M$ and have $K$ small rectangles in vertical orientation and $M$ in horizontal orientation. You want either the heights or the widths of the two rectangles to be close, but there is more searching to do.
answered Mar 30 at 4:28
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
Thanks very much for the detailed answer. I’ll try to absorb it in the morning - but to answer your question the width must be the short length (portrait orientation) and it may not be rotated. From a quick read of your answer, it seems that the problem was more difficult than I anticipated. Now I feel a little less stupid!
$endgroup$
– Jim
Mar 30 at 6:29
add a comment |
$begingroup$
I will assume all the small rectangles have to have the same orientation. It is already hard and I give a thought if this is not true at the end. Let the bounding rectangle be $W times H$. We are trying to choose a scale factor $s$ for the $39 times 83$ rectangles that is as large as possible so that we can fit $N$ scaled rectangles in the bounding one.
Assuming the small rectangles have to have the same orientation means the optimum tiling is rectangular. We just have to choose the orientation of the small rectangles and the number that fit across the width.
As a first cut, assume the small rectangles are oriented with the long axis horizontal. They are then $83s$ wide and $39s$ tall, so we get $lfloor frac W83s rfloor$ rectangles horizontally and $lfloor frac H39srfloor$ vertically. We need $lfloor frac W83s rfloorlfloor frac H39srfloorge N$ for the proper number to fit. We start by ignoring the floor signs, so we can find $s=sqrtfrac WH83cdot 39 N$. This just expresses the fact that the small rectangles have to have less area than the large one, ignoring any problems about whether they fit.
At this point you will only succeed if $frac W83s$ and $frac H39s$ are integers, so the outer rectangle is completely filled. You are lucky-declare victory! If not, you have an approximation $n=frac W83s$ to the number of small rectangles you want horizontally. If you place $m$ rectangles horizontally, you need $k=lceil frac Nm rceil$ rows. You can compute the scale factors in each direction as $frac W83m$ and $frac H39k$. Take the lower of these. Now search for the best $m$, which will be near the $n$ we computed above, based on finding the largest scale factor.
Repeat the process for the other orientation of the small rectangles, exchanging $39$ and $83$ and you have the answer under these restrictions.
If you don't insist that the small rectangles have the same orientation, you have one more degree of freedom. You can split $N$ into $N=K+M$ and have $K$ small rectangles in vertical orientation and $M$ in horizontal orientation. You want either the heights or the widths of the two rectangles to be close, but there is more searching to do.
answered Mar 30 at 4:28
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
Thanks very much for the detailed answer. I’ll try to absorb it in the morning - but to answer your question the width must be the short length (portrait orientation) and it may not be rotated. From a quick read of your answer, it seems that the problem was more difficult than I anticipated. Now I feel a little less stupid!
$endgroup$
– Jim
Mar 30 at 6:29
add a comment |
$begingroup$
I will assume all the small rectangles have to have the same orientation. It is already hard and I give a thought if this is not true at the end. Let the bounding rectangle be $W times H$. We are trying to choose a scale factor $s$ for the $39 times 83$ rectangles that is as large as possible so that we can fit $N$ scaled rectangles in the bounding one.
Assuming the small rectangles have to have the same orientation means the optimum tiling is rectangular. We just have to choose the orientation of the small rectangles and the number that fit across the width.
As a first cut, assume the small rectangles are oriented with the long axis horizontal. They are then $83s$ wide and $39s$ tall, so we get $lfloor frac W83s rfloor$ rectangles horizontally and $lfloor frac H39srfloor$ vertically. We need $lfloor frac W83s rfloorlfloor frac H39srfloorge N$ for the proper number to fit. We start by ignoring the floor signs, so we can find $s=sqrtfrac WH83cdot 39 N$. This just expresses the fact that the small rectangles have to have less area than the large one, ignoring any problems about whether they fit.
At this point you will only succeed if $frac W83s$ and $frac H39s$ are integers, so the outer rectangle is completely filled. You are lucky-declare victory! If not, you have an approximation $n=frac W83s$ to the number of small rectangles you want horizontally. If you place $m$ rectangles horizontally, you need $k=lceil frac Nm rceil$ rows. You can compute the scale factors in each direction as $frac W83m$ and $frac H39k$. Take the lower of these. Now search for the best $m$, which will be near the $n$ we computed above, based on finding the largest scale factor.
Repeat the process for the other orientation of the small rectangles, exchanging $39$ and $83$ and you have the answer under these restrictions.
If you don't insist that the small rectangles have the same orientation, you have one more degree of freedom. You can split $N$ into $N=K+M$ and have $K$ small rectangles in vertical orientation and $M$ in horizontal orientation. You want either the heights or the widths of the two rectangles to be close, but there is more searching to do.
answered Mar 30 at 4:28
Ross MillikanRoss Millikan
301k24200375
$endgroup$
I will assume all the small rectangles have to have the same orientation. It is already hard and I give a thought if this is not true at the end. Let the bounding rectangle be $W times H$. We are trying to choose a scale factor $s$ for the $39 times 83$ rectangles that is as large as possible so that we can fit $N$ scaled rectangles in the bounding one.
Assuming the small rectangles have to have the same orientation means the optimum tiling is rectangular. We just have to choose the orientation of the small rectangles and the number that fit across the width.
As a first cut, assume the small rectangles are oriented with the long axis horizontal. They are then $83s$ wide and $39s$ tall, so we get $lfloor frac W83s rfloor$ rectangles horizontally and $lfloor frac H39srfloor$ vertically. We need $lfloor frac W83s rfloorlfloor frac H39srfloorge N$ for the proper number to fit. We start by ignoring the floor signs, so we can find $s=sqrtfrac WH83cdot 39 N$. This just expresses the fact that the small rectangles have to have less area than the large one, ignoring any problems about whether they fit.
At this point you will only succeed if $frac W83s$ and $frac H39s$ are integers, so the outer rectangle is completely filled. You are lucky-declare victory! If not, you have an approximation $n=frac W83s$ to the number of small rectangles you want horizontally. If you place $m$ rectangles horizontally, you need $k=lceil frac Nm rceil$ rows. You can compute the scale factors in each direction as $frac W83m$ and $frac H39k$. Take the lower of these. Now search for the best $m$, which will be near the $n$ we computed above, based on finding the largest scale factor.
Repeat the process for the other orientation of the small rectangles, exchanging $39$ and $83$ and you have the answer under these restrictions.
If you don't insist that the small rectangles have the same orientation, you have one more degree of freedom. You can split $N$ into $N=K+M$ and have $K$ small rectangles in vertical orientation and $M$ in horizontal orientation. You want either the heights or the widths of the two rectangles to be close, but there is more searching to do.
answered Mar 30 at 4:28
Ross MillikanRoss Millikan
301k24200375
answered Mar 30 at 4:28
Ross MillikanRoss Millikan
301k24200375
answered Mar 30 at 4:28
Ross MillikanRoss Millikan
301k24200375
answered Mar 30 at 4:28
Ross MillikanRoss Millikan
301k24200375
301k24200375
$begingroup$
Thanks very much for the detailed answer. I’ll try to absorb it in the morning - but to answer your question the width must be the short length (portrait orientation) and it may not be rotated. From a quick read of your answer, it seems that the problem was more difficult than I anticipated. Now I feel a little less stupid!
$endgroup$
– Jim
Mar 30 at 6:29
add a comment |
$begingroup$
Thanks very much for the detailed answer. I’ll try to absorb it in the morning - but to answer your question the width must be the short length (portrait orientation) and it may not be rotated. From a quick read of your answer, it seems that the problem was more difficult than I anticipated. Now I feel a little less stupid!
$endgroup$
– Jim
Mar 30 at 6:29
$begingroup$
Thanks very much for the detailed answer. I’ll try to absorb it in the morning - but to answer your question the width must be the short length (portrait orientation) and it may not be rotated. From a quick read of your answer, it seems that the problem was more difficult than I anticipated. Now I feel a little less stupid!
$endgroup$
– Jim
Mar 30 at 6:29
$begingroup$
Thanks very much for the detailed answer. I’ll try to absorb it in the morning - but to answer your question the width must be the short length (portrait orientation) and it may not be rotated. From a quick read of your answer, it seems that the problem was more difficult than I anticipated. Now I feel a little less stupid!
$endgroup$
– Jim
Mar 30 at 6:29
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3167913%2fcalculate-resizing-factor-for-n-small-rectangles-inside-a-large-rectangle-to-cov%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
