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

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 对 coordinateForPhoto(width, height) 方法的请求:

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

我认为应该这样做。