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

Question

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

由于很容易有上千张照片需要一次计算位置，所以效率很重要。

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

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

Answer 1

一个矩阵（你的例子是 5x9）怎么样，其中每个单元格都有一个值代表到左上角的距离（例如（行+1）*（列+1）[+1是唯一必要的如果您的第一行和值是 0])。在此矩阵中，您寻找具有最低值的区域（当对空单元格的值求和时）。第二个矩阵（或第一个矩阵的第三个维度）存储每个单元格的状态。

编辑：

int[][] grid = new int[9][5];
int[] filledRows = new int [9];
int photowidth = 2;
int photoheight = 1;
int emptyRowCounter = 0;
boolean photoFits = true;

for(int i = 0; i < grid.length; i++){
    for(int m = 0; m < filledRows.length; m++){
        if(filledRows[m]-(photoHeight-1) > i || filledRows[m]+(photoHeight-1) < i){
            for(int j = 0; j < grid[i].length; j++){
                if(grid[i][j] == 0){
                    for(int k = 0; k < photowidth; k++){
                        for(int l = 0; k < photoheight){
                            if(grid[i+l][j+k]!=0){
                                photoFits = false;
                            }
                        }
                    }
                } else{
                    emptyRowCounter++;
                }
            }
            if(photoFits){
                //place Photo at i,j
            }
            if(emptyRowCounter == 5){
                filledRows[i] = 1;
            }
        }
    }
}

Answer 2

在您上面的 gif 中，结果很好地证明有一张照片 (5) 可以放入 (1) 下方和 (2) 左侧的空隙中。我的直觉表明我们希望避免产生这样的差距。这是一个应该避免这些差距的想法。

维护一个 "open regions" 列表，其中一个开放区域有一个 int leftBoundary、一个 int topBoundary 和一个可选的 int bottomBoundary。第一个开放区域就是整个网格 (leftBoundary:0, topBoundary: 0, bottom: null).

按高度排序照片，按宽度排序。

直到您放置了所有照片：

选择最高的照片（如果并列，请选择最高照片中最宽的照片）。找到它可以容纳的第一个开放区域（例如 grid.Width - region.leftBoundary >= photo.Width）。将照片放在该区域的左上角。当您放置这张照片时，它可能会横跨区域的整个宽度或高度。

如果跨越区域的宽度和高度，则区域被填充！从开放区域列表中删除该区域。
如果它跨越宽度，但不跨越高度，将照片的高度添加到该区域的 topBoundary。
如果它跨越了高度，但没有跨越宽度，则将照片的宽度添加到该区域的左边界。
如果它不跨越边界的高度或宽度，我们将在概念上将这个区域一分为二：一个区域将直接覆盖此右侧的space photo（称其为rightRegion），其他区域将覆盖该区域下方的space（称其为belowRegion）。

右区域={ 左边界 = parentRegion.leftBoundary + photo.width, topBoundary = parentRegion.topBoundary, 底部边界 = parentRegion.topBoundary + photo.height }

下方地区 = { 左边界 = 0, topBoundary = parentRegion.topBoundary + photo.height, 底部边界 = parentRegion.bottomBoundary }

将开放区域列表中的当前区域替换为rightRegion，并在rightRegion之后直接插入belowRegion。

您可以想象一下该算法如何处理您的示例：首先，它会对照片进行排序：(2,3,4,1,5)。

它考虑了 2，它适合第一个区域（整个网格）。当它把 2 放在左上角时，它将那个区域分割成直接在 2 右边的 space 和 2 下面的 space。

然后考虑3，依次考虑open regions。第一个开放区域在 2 的右侧。3 适合那里，所以它就是去的地方。它跨越区域的宽度，因此区域的 topBoundary 向下调整。

然后，它考虑 4。它再次适合第一个开放区域，所以它把 4 放在那里。 4 跨越区域的高度，因此区域的 leftBoundary 向右调整。

然后，1 被放入 4 右边的 1x1 空隙中，填满它的区域。最后，5 被放在 2 的正下方。

Answer 3

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

(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)

最终照片不会改变列表。

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

更新 响应@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 个连续的 space 可用，则之后仍然有 3 个连续的 space 可用）。范围 (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;
    }
}

我认为应该这样做。

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

efficiently calculate locations for rectangles in a unit grid

algorithm

layout

grid-layout