The following function calculates the maximum-sized tile for the given information.
If the fact that it's written in Python makes it hard for you to understand, let me know in a comment and I'll try to do it up in some other language.
import math
from __future__ import division
def max_tile_size(tile_count, rect_size):
"""
Determine the maximum sized tile possible.
Keyword arguments:
tile_count -- Number of tiles to fit
rect_size -- 2-tuple of rectangle size as (width, height)
"""
# If the rectangle is taller than it is wide, reverse its dimensions
if rect_size[0] < rect_size[1]:
rect_size = rect_size[1], rect_size[0]
# Rectangle aspect ratio
rect_ar = rect_size[0] / rect_size[1]
# tiles_max_height is the square root of tile_count, rounded up
tiles_max_height = math.ceil(math.sqrt(tile_count))
best_tile_size = 0
# i in the range [1, tile_max_height], inclusive
for i in range(1, tiles_max_height + 1):
# tiles_used is the arrangement of tiles (width, height)
tiles_used = math.ceil(tile_count / i), i
# tiles_ar is the aspect ratio of this arrangement
tiles_ar = tiles_used[0] / tiles_used[1]
# Calculate the size of each tile
# Tile pattern is flatter than rectangle
if tile_ar > rect_ar:
tile_size = rect_size[0] / tiles_used[0]
# Tile pattern is skinnier than rectangle
else:
tile_size = rect_size[1] / tiles_used[1]
# Check if this is the best answer so far
if tile_size > best_tile_size:
best_tile_size = tile_size
return best_tile_size
print max_tile_size(4, (100, 100))
The algorithm can loosely be described as follows
- If the rectangle is higher than it is wide, flip it so that it's wider than it is high.
- Calculate s, the square root of the number of tiles, rounded up. (Named
tiles_max_height in code.)
- Loop where i goes from 1 to s inclusive:
- Construct a grid of squares that is number of tiles / i squares wide and i squares high. (Round everything up. This "pads" the missing tiles, such as using 2 tiles by 2 tiles when your total number of tiles is 3.)
- Make this grid as big as possible. (Calculate this using aspect ratios.) Determine the size of one tile.
- Using that size, determine the total area covered by the tiles.
- Check if this is the best total area so far; if it is, store the square size
- Return that square size
This is probably one of the faster algorithms listed here, as it computes the best square size in O(sqrt(n)) for n tiles.
Update
On further consideration, this problem has a simpler solution based on the solution above. Say you are given 30 tiles. Your possible tile arrangements are easy to compute:
- 30 x 1 (aspect ratio 30.0000)
- 15 x 2 (aspect ratio 7.5000)
- 10 x 3 (aspect ratio 3.3333)
- 8 x 4 (aspect ratio 2.0000)
- 6 x 5 (aspect ratio 1.2000)
- 6 x 6 (aspect ratio 1.0000)
Say your rectangle is 100 x 60. Your rectangle's aspect ratio is 1.6667. This is between 1.2 and 2. Now, you only need to calculate the tile sizes for the 8 x 4 and the 6 x 5 arrangements.
The first step still technically takes O(sqrt(n)) though, so this updated method is not asymptotically faster than the first attempt.
Some updates from the comments thread
/*
Changes made:
tiles_used -> tiles_used_columns, tiles_used_rows
(it was originally a 2-tuple in the form (colums, rows))
*/
/* Determine the maximum sized tile possible. */
private function wesleyGetTileSize() : Number {
var tile_count : Number = slideCount.value;
var b : Number = heightOfBox.value;
var a : Number = widthOfBox.value;
var ratio : Number;
// // If the rectangle is taller than it is wide, reverse its dimensions
if (a < b) {
b = widthOfBox.value;
a = heightOfBox.value;
}
// Rectangle aspect ratio
ratio = a / b;
// tiles_max_height is the square root of tile_count, rounded up
var tiles_max_height : Number = Math.ceil(Math.sqrt(tile_count))
var tiles_used_columns : Number;
var tiles_used_rows : Number;
var tiles_ar : Number;
var tile_size : Number;
var best_tile_size : Number = 0;
// i in the range [1, tile_max_height], inclusive
for(var i: Number = 1; i <= tiles_max_height + 1; i++) {
// tiles_used is the arrangement of tiles (width, height)
tiles_used_columns = Math.ceil(tile_count / i);
tiles_used_rows = i;
// tiles_ar is the aspect ratio of this arrangement
tiles_ar = tiles_used_columns / tiles_used_rows;
// Calculate the size of each tile
// Tile pattern is flatter than rectangle
if (tiles_ar > ratio){
tile_size = a / tiles_used[0] ;
}
// Tile pattern is skinnier than rectangle
else {
tile_size = b / tiles_used[1];
}
// Check if this is the best answer so far
if (tile_size > best_tile_size){
best_tile_size = tile_size;
}
}
returnedSize.text = String(best_tile_size);
return best_tile_size;
}