Wow!
I just tried your algorithm with my previous example numbers and it does
output the correct square size (100) - also, internally it has the right
number of columns/lines: e.g. 3x4 (p=3, q=4) As for performance, it took 6
iterations: Since the output was 3x4, the number of iterations was (3 + 4 -
1) = 6. (it started at 1x1 and did 6 iterations: something like: 1x1, 1x2,
2x2, 2x3, 3x3, 3x4)
For N = 100, the number of iteration depends on the ratio: it could be
anywhere from 19 (10x10-1) to 100 iterations (worst case happens if the
output is a single line or a single column). So that would make N
iterations (in worst cases) and ~2*SQRT(N)-1 best case.
I took the liberty of optimizing the method a little bit and renaming a few
internal variables to my personal liking. ;-) -- I did not do any "real
life" testing on this. But it seems to work on paper.
/**
* computes the largest N square size (and layout) that can fit an area
(width,height).
*
* @return an Object containing 'squareSize' and the number of 'cols' and
'rows'.
*
* 98% of the credits goes to Danny Kodicek
*/
function computeLargestSquareSizeAndLayout(width:Number, height:Number,
Nsquares:Number): Object
{
var cols:Number = 1;
var rows:Number = 1;
var swidth:Number = width;
var sheight:Number = height;
var next_swidth:Number = width/(cols+1);
var next_sheight:Number = height/(rows+1);
while (true)
{
if (cols*rows >= Nsquares)
{
var squareSize:Number = Math.min(swidth, sheight);
return { squareSize:squareSize, cols:cols, rows:rows };
}
if (next_swidth > next_sheight)
{
cols++;
swidth = next_swidth;
next_swidth = width/(cols+1);
}
else
{
rows++;
sheight = next_sheight;
next_sheight = height/(rows+1);
}
}
}
B.
2006/5/8, Danny Kodicek <[EMAIL PROTECTED]>:
>Danny: I do not understand your algorithm - could you shed some more
(high-level) light on what it is doing?
Sure. The idea is that the optimal size will always be an exact fraction
of
either the width or the height. So what we do is drop down by multiples of
these until we get to the first size that will contain N or more squares.
At
any particular width, we keep track of the two 'next-smallest' widths and
drop down to the largest of these. Run through the algorithm with a few
sample numbers and it should make sense.
It may be that there's a more algebraic approach. The problem is, though,
that there is no simple relationship between floor(x), floor(y) and
floor(xy), which would be needed to come up with any truly useful
solution.
In the end, it turns into quite a complex optimisation problem, and given
that the brute force algorithm is actually pretty fast, it hardly seems
worth the effort :)
Danny
_______________________________________________
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
_______________________________________________
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
