CODEWITHSUNDEEP
algorithmmathgrid
sevenflow
sevenflow

Reputation: 777

Create an optimal grid based on n-items, total area, and H:W ratio

I'm creating an application that takes a number of equally sized rectangles and positions them in a grid on the screen. I have most of the logic complete for resizing and centering a rectangle within a cell but I'm having trouble with the actual portion that defines the grid the rectangles must conform to.

Ideally, in the end I'd have a function like this (pseudo-code):


function getGridDimensions (rect surface, int numItems, float hwRatio) {
    // do something to determine grid-height and grid-width
    return gridDimensions;
}

My original stab at this involved something like this:


gridHeight = surface.width / sqrt(numItems);
gridWidth = surface.height / sqrt(numItems);

This would work nicely if my items were all perfect squares, but since they're rectangles there is a lot of unused white space within each cell.

Any thoughts or terms to Google that could point me in the right direction?

Upvotes: 16

Views: 5318

Answers (2)

Vik
Vik

Reputation: 730

So I think I have an algorithm that can get an optimal answer via brute force. This should still be reasonably fast upto 100-1000 items. Here is the algorithm in python. It basically iterates through all ways of spreading the items into rows and columns and then picks the one with the best efficiency.

def calculate_best_screen_packing(N, img_resolution = (800,600), screen_resolution = (1920, 1080)):    
    screen_x = screen_resolution[0]
    screen_y = screen_resolution[1]
    screen_area = screen_x * screen_y

    img_x = img_resolution[0]
    img_y = img_resolution[1]
    img_aspect = img_x / img_y

    best_dims = (None,None)
    best_eff = 0.0

    for n_rows in range(1,N//2 +1):
        #print(i)
        n_cols = N // n_rows
        if N % n_rows != 0: n_cols = n_cols+1

        #print(n_rows, n_cols)

        # Test by maximising image height        
        img_y_scaled = screen_y / n_rows
        img_x_scaled = img_y_scaled * img_aspect
        img_area_scaled = img_x_scaled * img_y_scaled
        eff = img_area_scaled * N / screen_area
        #print(img_x_scaled, img_y_scaled, eff)

        if eff <= 1.0 and eff > best_eff:
            best_eff = eff
            best_dims = (n_rows, n_cols)

        # Test by maximising image width                
        img_x_scaled = screen_x / n_cols
        img_y_scaled = img_x_scaled / img_aspect
        img_area_scaled = img_x_scaled * img_y_scaled
        eff = img_area_scaled * N / screen_area
        #print(img_x_scaled, img_y_scaled, eff)
        if eff <= 1.0 and eff > best_eff:
            best_eff = eff
            best_dims = (n_rows, n_cols)

    #print("Best dims:",best_dims,best_eff)
    return best_dims

Upvotes: 0

Chris
Chris

Reputation: 27629

I'm a bit unclear on some of your input parameters but I'm assuming that you have Rectangle height and width, the number of rectangles and the ideal height-width ratio (ie preferred gridheight/gridwidth).

If this is the case then I'd probably start off by "normalizing" your dimensions so for the purpose of the following calculations we say a unit of width is the same as the width of a rectangle and likewise for a unit of height. If your height/width ratio in real units was k then your height/width ratio in Rectange units would be k*RectWidth/RectHeight. I'll call this K.

So now each rectangle by definition has an area of 1 so our total area is N where N is the number of items. We can then approximate our height add width to give ourselves our preferred grid aspect ratio by saying gridHeight*gridWidth = N and gridHeight/gridWidth = K

With these we get gridHeight = sqrt(KN) and gridWidth = sqrt(N/K).

If you round one of these off to a suitable whole number (I'm not sure ifwhichever is nearest a whole number rounded will give you the best result or if its whichever rounding will give the smallest percentage change in that value is best - you can always try all four if you care that much). Once you have one integer value you then calculate the other by finding the smallest integer that can multipy the other and still be greater than N to make sure you fit all rectanges in the grid).

You can then of course change your integer values back to real ones by multiply the height by rectHeight and the wdith by RectWidth.

Hopefully that all makes sense. :)

Edit for worked example:

Required final grid aspect ratio = 1024/768 (k) (assumes that 768 is width and 1024 is height - I kept wanting to put it the other way around as a standard screen resolution :) )

"Normalised" aspect ratio = (1024/768) * (300/109) = 3.6697 (K)

Grid Height therefore is sqrt(KN) = sqrt(366.97) = 19.16

Grid Width is sqrt(N/K) = 5.22

Looking at this we can see intuitively that width 5 and height 20 will be our best match. The other options might be 6 and 19. But that will waste more space (I think possibly actually minimizing the product of the width and height here migth be the best calculation but I'm not sure).

This is now our grid size in cells. This then scales up to pixel dimensions of 1500 by 2180. Scaling down to fit in 768x1024 means dividing both by 2.129 (the larger of 1500/768 and 2180/1024). So your images will scale down by 2.129 times to 141x51(ish) and your total area used will actually be 705x1020 which should give minimal whitespace.

Hopefully that makes more sense now. I'll admit, I went wrong a few times putting real values in so I totally understand why you wanted a worked example. ;-)

Upvotes: 20

Related Questions