0
$\begingroup$

A geometry question that I feel utterly defeated by. I'm trying to design a responsive user interface that efficiently fits a variable number of square elements on a screen, by adjusting the size of the squares. With a known square size, the number of squares along and up will be implicit. I'm also very interested to know the answer.

I describe the problem as thus:

A known number of squares, n, must be fit as efficiently as possible (least remaining area) into a rectangle of known dimensions x & y. The dimension (equal width and height) of the squares, s, must be adjusted to achieve this. The squares must be axis-aligned. Find s.

All I've been able to establish is that where n/(w/h) is an integer, n + 1 is a worst case scenario of remainder. I can't seem to get any more facts to come out in the wash, but am interested in the working of the answer.

Update:

I've worked out (I hope), the maximum number of squares that may be fit, as follows:

max squares =
( floor( longest side / shortest side ) * divisor^2 ) +
( floor( r / ( shortest side / divisor ) ) * divisor )

Based on fitting squares with a size of the shortest side of the rectangle, dividing them down by the divisor (iteratively until enough squares are achieved), each time seeing how much of the remainder can be occupied by the divided down dimension.

Now I just need to turn this into a single formula so it doesn't have to be computed iteratively, if possible.

$\endgroup$
  • $\begingroup$ If I follow it right, $s=1$ will have no remaining area, but is there a balance between square size and remaining area? $\endgroup$ – Empy2 May 19 '16 at 15:52
  • $\begingroup$ All squares must be the same size. The problem is to find a size where all squares fit the rectangle, with the least possible remainder of space. In some cases there might be no remainder at all; e.g. a rectangle of width 4 units and height 2 units, of which 8 squares must be fit, in which case s = 1 unit. If the width were increased to 4.1 units the solution would be the same, but there would now be a remainder of 0.2 units^2. $\endgroup$ – Toby Wilson May 20 '16 at 7:59
0
$\begingroup$

I'm decently sure this can be accomplished by simply adding the largest possible square i.e. has the minimum of width or height as side length. put square on side of rectangle and you end with a rectangle demension $x$ and $y-x$ without loss of generality. then simply repeat until either there's no remainder or your out of number of squares.

$\endgroup$
  • $\begingroup$ Sorry, I should have made this clear; all squares must be the same size. The problem is finding that size, where all of them fit the rectangle with the least possible remainder. $\endgroup$ – Toby Wilson May 20 '16 at 7:53
  • $\begingroup$ @TobyWilson Ah ok that adds a degree of complexity let me think about that. $\endgroup$ – shai horowitz May 20 '16 at 7:54
  • $\begingroup$ @TobyWilson Are any of the variables known or are "known" values simply constants $\endgroup$ – shai horowitz May 20 '16 at 7:57
  • $\begingroup$ Known values (constants): Width and height of the rectangle, and the number of equal squares that must be fit into that rectangle. Unknown value: Size of those squares, where the size is such that there will be the least possible empty space left in the rectangle. $\endgroup$ – Toby Wilson May 20 '16 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.