If I have a set of tiles (squares) which can be any number and they are to fill a container (rectangle) of an unknown size how do I work out the maximum size of the tiles without having any of them overlap.
So if I have 2 tiles and the rectangle is 100 * 100 then the max tile size is 50 * 50. This would also be the max size of tile if there was 3 or 4 tiles for this size of rectanlgle, which just so happens to be a square in this example.
If the rectanlge was 100 * 30 and I had 2 tiles, the max size of the square would be 30 * 30, if I have 4 tiles the max size would be 25 * 25.
How can I do this programatically without hogging the processor by going through every possible combination.
I try to summarise a bit better, I have a:
rectangle/bounding box that I need to fill as much as possible without the tiles overlapping.
I know the height and width of the rectangle (but this can change during runtime).
I have X number of tiles (this can change at run time), these are squares.
None of the tiles should overlap, what is the maximum size that each tile can be. They are all to be the same size.
I've managed to come up with a 'relatively' optimal solution. Partially based on Zac's pseudocode answer.
//total number of tiles
var tile_count : Number = numberOfSlides;
//height of rectangle
var b : Number = unscaledHeight;
//width of rectanlge
var a : Number = unscaledWidth;
//divide the area but the number of tiles to get the max area a tile could cover
//this optimal size for a tile will more often than not make the tiles overlap, but
//a tile can never be bigger than this size
var maxSize : Number = Math.sqrt((b * a) / tile_count);
//find the number of whole tiles that can fit into the height
var numberOfPossibleWholeTilesH : Number = Math.floor(b / maxSize);
//find the number of whole tiles that can fit into the width
var numberOfPossibleWholeTilesW : Number = Math.floor(a / maxSize);
//works out how many whole tiles this configuration can hold
var total : Number = numberOfPossibleWholeTilesH * numberOfPossibleWholeTilesW;
//if the number of number of whole tiles that the max size tile ends up with is less than the require number of
//tiles, make the maxSize smaller and recaluate
while(total < tile_count){
maxSize--;
numberOfPossibleWholeTilesH = Math.floor(b / maxSize);
numberOfPossibleWholeTilesW = Math.floor(a / maxSize);
total = numberOfPossibleWholeTilesH * numberOfPossibleWholeTilesW;
}
return maxSize;
What this does is to work out the total area of the rectanlge, then divide it by the required number of tiles. As each tile is a square I can SQRT this so that I get the max size of the optimal tile.
With this optimal size I then check to see how many WHOLE tiles I can fit into the width & height. Multiply these together and if it is less than the required number of tiles then I reduce the optimal size and perform the checking again until all of the tiles fit the rectanlge.
I could optimise this further by doing something like reduce the optimal size by -2 insted of -1 each time and then if all the tiles fit increase by 1 just to make sure that I've not missed a valid size. or I could jump back more than -2, say -10 then if they all tiles fit increase by 5, then if the don't fit reduce by -2 etc until I get an optimal fit.
Check out http://kennethsutherland.com/flex/stackover/SlideSorterOK.html for my example. Thanks for all the various info.