efficiently calculate locations for rectangles in a unit grid

Question

I'm working on a specific layout algorithm to display photos in a unit based grid. The desired behaviour is to have every photo placed in the next available space line by line.

Since there could easily be a thousand photos whose positions need to be calculated at once, efficiency is very important.

Has this problem maybe been solved with an existing algorithm already? If not, how can I approach it to be as efficient as possible?

Edit Regarding the positioning: What I'm basically doing right now is iterating every line of the grid cell by cell until I find room to fit the element. That's why 4 is placed next to 2.

Answer 1

How about keeping a list of next available row by width? Initially the next-available-row list looks like:

(0,0,0,0,0)

When you've added the first photo, it looks like

(0,0,0,0,1)

Then

(0,0,0,2,2)

Then

(0,0,0,3,3)

Then

(1,1,1,4,4)

And the final photo doesn't change the list.

This could be efficient because you're only maintaining a small list, updating a little bit at each iteration (versus searching the entire space every time. It gets a little complicated - there could be a situation (with a tall photo) where the nominal next available row doesn't work, and then you could default to the existing approach. But overall I think this should save a fair amount of time, at the cost of a little added complexity.

Update In response to @matteok's request for a coordinateForPhoto(width, height) method:

Let's say I called that array "nextAvailableRowByWidth".

public Coordinate coordinateForPhoto(width, height) {
    int rowIndex = nextAvailableRowByWidth[width + 1]; // because arrays are zero-indexed
    int[] row = space[rowIndex]
    int column = findConsecutiveEmptySpace(width, row);
    for (int i = 1; i < height; i++) {
        if (!consecutiveEmptySpaceExists(width, space[i], column)) {
            return null;
            // return and fall back on the slow method, starting at rowIndex
        }
    }
    // now either you broke out and are solving some other way,
    // or your starting point is rowIndex, column.  Done.
    return new Coordinate(rowIndex, column);
}

Update #2 In response to @matteok's request for how to update the nextAvailableRowByWidth array:

OK, so you've just placed a new photo of height H and width W at row R. Any elements in the array which are less than R don't change (because this change didn't affect their row, so if there were 3 consecutive spaces available in the row before placing the photo, there are still 3 consecutive spaces available in it after). Every element which is in the range (R, R+H) needs to be checked, because it might have been affected. Let's postulate a method maxConsecutiveBlocksInRow() - because that's easy to write, right?

public void updateAvailableAfterPlacing(int W, int H, int R) {
    for (int i = 0; i < nextAvailableRowByWidth.length; i++) {
        if (nextAvailableRowByWidth[i] < R) {
            continue;
        }
        int r = R;
        while (maxConsecutiveBlocksInRow(r) < i + 1) {
            r++;
        }
        nextAvailableRowByWidth[i] = r;
    }
}

I think that should do it.