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

user_424107 0
Viewed 4434

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?

math grid algorithm
2 Answers

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
user_83712070
Related