有效计算单位网格中矩形的位置

Question

我正在研究一种特定的布局算法，以在基于单元的网格中显示照片。理想的行为是将每张照片逐行放置在下一个可用空间中。

由于很容易有一千张照片需要同时计算位置，因此效率非常重要。

这个问题是否已经用现有算法解决了？如果没有，我怎样才能尽可能高效地实现它？

编辑关于定位：我现在基本上所做的就是逐个单元地迭代网格的每一行，直到找到适合该元素的空间。这就是为什么 4 放在 2 旁边。

Answer 1

如何按宽度保留下一个可用行的列表？最初，下一个可用行列表如下所示：

(0,0,0,0,0)

添加第一张照片后，它看起来像

(0,0,0,0,1)

然后

(0,0,0,2,2)

然后

(0,0,0,3,3)

然后

(1,1,1,4,4)

最终的照片不会改变列表。

这可能会很有效，因为您只维护一个小列表，在每次迭代时更新一点（而不是每次搜索整个空间）。它变得有点复杂 - 可能存在一种情况（带有高照片），标称值下一个可用行不起作用，然后您可以默认使用现有方法。但总的来说，我认为这应该节省相当多的时间，但代价是增加了一点复杂性。

更新 响应@matteok对坐标ForPhoto（宽度，高度）方法的请求：

假设我将该数组称为“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);
}

更新 #2 响应 @matteok 关于如何更新 nextAvailableRowByWidth 数组的请求：

好的，所以您刚刚在 R 行放置了一张高度 H 和宽度 W 的新照片。数组中小于 R 的任何元素都不会更改（因为此更改不会影响它们的行，所以如果有放置照片之前该行有 3 个连续的空格，之后仍然有 3 个连续的空格）。需要检查 (R, R+H) 范围内的每个元素，因为它可能已受到影响。让我们假设一个方法 maxConsecutiveBlocksInRow() - 因为这很容易编写，对吗？

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;
    }
}

我认为应该这样做。