0

Squares should all have the same dimension. The ratio constraint is that the length of the rectangle should be equal to its width (a square) or no more than two times its width (2:1 ratio). The algorithm should minimize the uncovered area. For the same uncovered area, a ratio closer or equal to 2:1 should be preferred.

I can't wrap my head around it. :) The practical aim is to automate the creation of an image, the square tiles are pictures. There can be 1 square to no more than a couple hundreds so I could brute force all the possibilities and check for constraints but is there a more elegant solution?

Thanks.

jeromecc
  • 1
  • The number of tiles is easily calculated -- see https://math.stackexchange.com/q/2482236/139123 -- and they can simply be arranged in a regular grid that fits inside the rectangle. The same method that tells you how many tiles also tells you the dimensions of that grid. There will essentially be only one arrangement, although if there is uncovered area you have some freedom to move the tiles and create gaps between them. – David K Oct 26 '22 at 05:26
  • You can use continued fractions to get the best rational approximations $p/q$ to the rectangle's ratio. Then try an arrangement of $p\times q$ squares. However, since you are only going up to hundreds of squares, it is probably easier and less error-prone to just brute force it. – Jaap Scherphuis Oct 26 '22 at 09:11

0 Answers0