7
$\begingroup$

Suppose you have a rectangle that is w units wide and h units tall (bounding rectangle). You also have an even n number of rectangles (objects) that have a fixed aspect ratio and will scale linearly to fit the height of the bounding rectangle. Is there an algorithm or function that would produce the needed grid size of the objects packed into the bounded box so that the space consumed of the bounding rectangle by objects is maximized?

If that question doesn't make sense, then I agree, because I think I confused myself trying to write it. So I'm going to try again:

Lets say I have a table that I am going to play cards on. I know that the table top is w inches wide and h inches long. I start placing an even n number of cards on the table in rows and columns until I have a grid of cards on the table. The cards I'm using have a neat trick so that once they have all been placed on the table, each card will magically grow in size keeping the aspect ratio of the original card size while the grow. The cards stop growing once once the top edge of the cards in the top row and the bottom edge of the cards in the bottom row touch the edges of the table. Now I don't want any of the cards to fall off the right or left side of the table when they grow, so how do I figure out how many rows and columns I should lay out the cards initially so that when they finish growing, all the cards are as big as they can be and take up most of the table top?

I promise this isn't homework or anything like that, I'm writing a game in Unity and I'm trying to figure out how best to place my GameObjects in the camera's view so that they consume most of the camera's viewport.

EDIT:

So I have been working on this problem for a bit now, I have figured out a way to brute-force the computation of the grid size, however I have found a few edge cases where it doesn't seem to be working properly. I am finding that the resulting grid dimensions for vertically oriented screens $(\frac wh\lt 1)$ is laying out the cards in a "not pretty" way:

5x7 Scene and Game view in Unity

As you can see the cards in the bottom row should easily fit in the last column for a grid size of 5x6. However, the aspect ratio of a 5x6 grid of cards is greater than the aspect ratio of the camera's view:

5x6 Scene and Game view in Unity

I believe this to be happening because the cards are scaling with the height before the width, whereas if they were to scale width first, then they would grow to the proper size. Banging my head on the wall here, please assist me in figuring out how to change my algorithm to account for this variation?

I know this isn't a programming site, and may be starting to cross-over into the realm of StackOverflow... I'll save all of the non-programmers the C# code and try to write the algorithm out in pseudo code. I'll also include full C# code for those that would like to evaluate

pseudo code:
for all $possibleHeight$s from $1$ to $totalCards$ do
{
  get corresponding $possibleWidth$ from $\lceil\frac {totalCards}{possibleHeight}\rceil$
  get the $gridAspectRatio$ by multiplying the card's aspect ratio to $\frac {grid\ column\ count}{grid\ row\ count}$
  if $\left(possibleHeight \cdot possibleWidth \geqq totalcards\right)$ then
 {
   if $\left(gridAspectRatio \leqq playFieldAspectRatio \right)$ then
  {
   return $possibleWidth$ and $possibleHeight$ as the playFieldSize
  }
 }
}



C# code:

PlayField.PlayFieldSize PlayFieldLayout(int cardCount)
    {
        int w = 0;
        int h = 0;
        float playFieldAR = Camera.main.aspect; 

        for (int possibleHeight = 1; possibleHeight <= cardCount-1; possibleHeight++)
        {
            int possibleWidth = Mathf.CeilToInt((float)cardCount / (float)possibleHeight);
            float gridAR = ((float)possibleWidth / (float)(possibleHeight))* cardOffset.aspectRatio;
            if ((possibleHeight * possibleWidth) >= cardCount & playFieldAR >= gridAR){ w = possibleWidth; h = possibleHeight; break; }

        }

        return new PlayField.PlayFieldSize(Width: w, Height: h);
    }
$\endgroup$
0
$\begingroup$

Your problem is not well-defined mathematically, because you do not exactly define the subjective "not pretty way". In order to fix this you need to give us an exact definition of how "pretty" any given arrangement is, by defining a "prettiness function".

Assuming you have done that, fixing your code is simple.

You should change your algorithm to loop over all the "possible grid heights". Breaking out of the loop as you do is wrong. Just keep track of the best value of prettiness in addition to the best grid height, so you can check if another grid height is "prettier" than the best one found up to that point.

As for the prettiness function itself, possibly you might want to consider using $-\lvert playFieldAR - gridAR\rvert$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.