Resizing N # of squares to be as big as possible while still fitting into box of X by Y dimensions. (Thumbnails!)

I have N squares. I have a Rectangular box. I want all the squares to fit in the box. I want the squares to be as large as possible.

How do I calculate the largest size for the squares such that th开发者_如何学Cey all fit in the box?

This is for thumbnails in a thumbnail gallery.

int function thumbnailSize(
    iItems, // The number of items to fit.
    iWidth, // The width of the container.
    iHeight, // The height of the container.
    iMin // The smallest an item can be.
)
{
    // if there are no items we don't care how big they are!    
    if (iItems = 0) return 0;

    // Max size is whichever dimension is smaller, height or width.
    iDimension = (iWidth min iHeight);

    // Add .49 so that we always round up, even if the square root
    // is something like 1.2.  If the square root is whole (1, 4, etc..)
    // then it won't round up.
    iSquare = (round(sqrt(iItems) + 0.49));

    // If we arrange our items in a square pattern we have the same
    // number of rows and columns, so we can just divide by the number
    // iSquare, because iSquare = iRows = iColumns.
    iSize = (iDimension / iSquare);

    // Don't use a size smaller than the minimum.
    iSize = (iSize max iMin);

    return iSize;
 }

This code currently works OK. The idea behind it is to take the smallest dimension of the rectangular container, pretend the container is a square of that dimension, and then assume we have an equal number of rows and columns, just enough to fit iItems squares inside.

This function works great if the container is mostly squarish. If you have a long rectangle, though, the thumbnails come out smaller than they could be. For instance, if my rectangle is 100 x 300, and I have three thumbnails, it should return 100, but instead returns 33.

Probably not optimal (if it works which I haven't tried), but I think better than you current approach :

w: width of rectangle

h: height of rectangle

n: number of images

a = w*h : area of the rectangle.

ia = a/n max area of an image in the ideal case.

il = sqrt(ia) max length of an image in the ideal case.

nw = round_up(w/il): number of images you need to stack on top of each other.

nh = round_up(h/il): number of images you need to stack next to each other.

l = min(w/nw, w/nh) : length of the images to use.

The solution on https://math.stackexchange.com/a/466248 works perfectly.

An unoptimized javascript implementation:

var getMaxSizeOfSquaresInRect = function(n,w,h) 
{
    var sw, sh;
    var pw = Math.ceil(Math.sqrt(n*w/h));
    if (Math.floor(pw*h/w)*pw < n) sw = h/Math.ceil(pw*h/w);
    else sw = w/pw;
    var ph = Math.ceil(Math.sqrt(n*h/w));
    if (Math.floor(ph*w/h)*ph < n) sh = w/Math.ceil(w*ph/h);
    else sh = h/ph;
    return Math.max(sw,sh);
}

I was looking for a similar solution, but instead of squares I had to fit rectangles in the container. Since a square is also a rectangle, my solution also answers this question.

I combined the answers from Neptilo and mckeed into the fitToContainer() function. Give it the number of rectangles to fit n, the containerWidth and containerHeight and the original itemWidth and itemHeight. In case items have no original width and height, use itemWidth and itemHeight to specify the desired ratio of the items.

For example fitToContainer(10, 1920, 1080, 16, 9) results in {nrows: 4, ncols: 3, itemWidth: 480, itemHeight: 270}, so four columns and 3 rows of 480 x 270 (pixels, or whatever the unit is).

And to fit 10 squares in the same example area of 1920x1080 you could call fitToContainer(10, 1920, 1080, 1, 1) resulting in {nrows: 2, ncols: 5, itemWidth: 384, itemHeight: 384}.

function fitToContainer(n, containerWidth, containerHeight, itemWidth, itemHeight) {
    // We're not necessarily dealing with squares but rectangles (itemWidth x itemHeight),
    // temporarily compensate the containerWidth to handle as rectangles
    containerWidth = containerWidth * itemHeight / itemWidth;
    // Compute number of rows and columns, and cell size
    var ratio = containerWidth / containerHeight;
    var ncols_float = Math.sqrt(n * ratio);
    var nrows_float = n / ncols_float;

    // Find best option filling the whole height
    var nrows1 = Math.ceil(nrows_float);
    var ncols1 = Math.ceil(n / nrows1);
    while (nrows1 * ratio < ncols1) {
        nrows1++;
        ncols1 = Math.ceil(n / nrows1);
    }
    var cell_size1 = containerHeight / nrows1;

    // Find best option filling the whole width
    var ncols2 = Math.ceil(ncols_float);
    var nrows2 = Math.ceil(n / ncols2);
    while (ncols2 < nrows2 * ratio) {
        ncols2++;
        nrows2 = Math.ceil(n / ncols2);
    }
    var cell_size2 = containerWidth / ncols2;

    // Find the best values
    var nrows, ncols, cell_size;
    if (cell_size1 < cell_size2) {
        nrows = nrows2;
        ncols = ncols2;
        cell_size = cell_size2;
    } else {
        nrows = nrows1;
        ncols = ncols1;
        cell_size = cell_size1;
    }

    // Undo compensation on width, to make squares into desired ratio
    itemWidth = cell_size * itemWidth / itemHeight;
    itemHeight = cell_size;
    return { nrows: nrows, ncols: ncols, itemWidth: itemWidth, itemHeight: itemHeight }
}

The JavaScript implementation form mckeed gave me better results then the other answers I found. The idea to first stretch the rectangle to a square came from Neptilo.

you want something more like

n = number of thumbnails x = one side of a rect y = the other side l = length of a side of a thumbnail

l = sqrt( (x * y) / n )

Here is my final code based off of unknown (google)'s reply: For the guy who wanted to know what language my first post is in, this is VisualDataflex:

Function ResizeThumbnails Integer iItems Integer iWidth Integer iHeight Returns Integer
    Integer iArea iIdealArea iIdealSize iRows iCols iSize  
    // If there are no items we don't care how big the thumbnails are!
    If (iItems = 0) Procedure_Return
    // Area of the container.
    Move (iWidth * iHeight) to iArea
    // Max area of an image in the ideal case (1 image).
    Move (iArea / iItems) to iIdealArea
    // Max size of an image in the ideal case.
    Move (sqrt(iIdealArea)) to iIdealSize
    // Number of rows.
    Move (round((iHeight / iIdealSize) + 0.50)) to iRows
    // Number of cols.
    Move (round((iWidth / iIdealSize) + 0.50)) to iCols
    // Optimal size of an image.
    Move ((iWidth / iCols) min (iHeight / iRows)) to iSize
    // Check to make sure it is at least the minimum.
    Move (iSize max iMinSize) to iSize
    // Return the size
    Function_Return iSize
End_Function

This should work. It is solved with an algorithm rather than an equation. The algorithm is as follows:

• Span the entire short side of the rectangles with all of the squares
• Decrease the number of squares in this span (as a result, increasing the size) until the depth of the squares exceeds the long side of the rectangle
• Stop when the span reaches 1, because this is as good as we can get.

Here is the code, written in JavaScript:

function thumbnailSize(items, width, height, min) {

  var minSide = Math.min(width, height),
      maxSide = Math.max(width, height);

  // lets start by spanning the short side of the rectange
  // size: the size of the squares
  // span: the number of squares spanning the short side of the rectangle
  // stack: the number of rows of squares filling the rectangle
  // depth: the total depth of stack of squares
  var size = 0;
  for (var span = items, span > 0, span--) {
    var newSize = minSide / span;
    var stack = Math.ceil(items / span);
    var depth = stack * newSize; 
    if (depth < maxSide)
      size = newSize;
    else 
      break;
  }
  return Math.max(size, min);
}

In Objective C ... the length of a square side for the given count of items in a containing rectangle.

int count = 8;    // number of items in containing rectangle
int width = 90;   // width of containing rectangle
int height = 50;  // width of container
float sideLength = 0; //side length to use.


float containerArea = width * height;
float maxArea = containerArea/count;
float maxSideLength = sqrtf(maxArea);  
float rows = ceilf(height/maxSideLength);   //round up
float columns = ceilf(width/maxSideLength); //round up

float minSideLength = MIN((width/columns), (height/rows));
float maxSideLength = MAX((width/columns), (height/rows));

// Use max side length unless this causes overlap 
if (((rows * maxSideLength) > height) && (((rows-1) * columns) < count) ||
    (((columns * maxSideLength) > width) && (((columns-1) * rows) < count))) {
    sideLength = minSideLength;
}
else {
    sideLength = maxSideLength;
}

My JavaScript implementation:

var a = Math.floor(Math.sqrt(w * h / n));
return Math.floor(Math.min(w / Math.ceil(w / a), h / Math.ceil(h / a)));

Where w is width of the rectangle, h is height, and n is number of squares you want to squeeze in.

  double _getMaxSizeOfSquaresInRect(double numberOfItems, double parentWidth, double parentHeight) {
    double sw, sh;

    var pw = (numberOfItems * parentWidth / parentHeight).ceil();

    if ((pw * parentHeight / parentWidth).floor() * pw < numberOfItems) {
      sw = parentHeight / (pw * parentHeight / parentWidth).ceil();
    } else {
      sw = parentWidth / pw;
    }
    var ph = (sqrt(numberOfItems * parentHeight / parentWidth)).ceil();
    if ((ph * parentWidth / parentHeight).floor() * ph < numberOfItems) {
      sh = parentWidth / (parentWidth * ph / parentHeight).ceil();
    } else {
      sh = parentHeight / ph;
    }
    return max(sw, sh);
  }