为多维数组计算 "bounding box"

Question

所以我们有一个像这样的 5x5 二维数组：

gridmodel:
[
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

这表示块状对象的外观以及它在网格上的绘制方式，因此我们可以有这样的示例：

gridmodel:
[
    [0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

这将代表来自俄罗斯方块的简单 T 形块。如果形状不是从左上角开始，形状只是在运行时移动，所以它可以正常工作。

无论如何，这有点无关紧要。我需要的是一种计算此 5x5 网格中任何形状的边界框的方法。形状可以有孔，或者形状可以只包含数组中的单个 1，基本上 5x5 可以是 1 和 0 的任意组合。

为了计算边界框，我想我只需要找出哪个 1 是最顶部和最左侧，哪个 1 是最右侧和最底部。

这是我做的，它应该找到左上角的 1:

var bb = 
{ 
    x1: null, 
    y1: null,
    x2: null,
    y2: null
}

var toppest = null;
var leftest = null;

for(var y = 0; y < gridmodel.length; y++)
{
    for(var x = 0; x < gridmodel[y].length; x++)
    {
        if(gridmodel[y][x] === 1)
        {
            if(toppest === null)
            {
                toppest = { x: x, y: y };
            }

            if(leftest === null)
            {
                leftest = { x: x, y: y };
            }
            else
            {
                if(x < leftest.x)
                {
                    leftest = { x: x, y: y };
                }
            }
        }
    }
}

但这看起来已经太复杂了，几乎解决了一半的问题。

Answer 1

与您的想法差不多，但您只需要 1 个数字即可。您可以检查默认值 (max val, -1) 以查看是否找到任何内容。

var topmost = Number.MAX_VALUE;
var leftmost = Number.MAX_VALUE;
var bottommost = -1;
var rightmost = -1;

for(var y = 0; y < gridmodel.length; y++)
{
  var l = gridmodel[y].indexOf(1);
  var r = gridmodel[y].lastIndexOf(1);

  if (l >= 0 && l < leftmost) leftmost = l;
  if (r >= 0 && r > rightmost) rightmost = r;

  // only check if some 1 found
  if (l >= 0 && y < topmost) topmost = y;
  if (l >= 0 && y > bottommost) bottommost = y;
}

bb = {x1: leftmost, y1: topmost, x2: rightmost, y2: bottommost};

为多维数组计算 "bounding box"

Calculate "bounding box" for multidimensional array

javascript

arrays

algorithm

bounding-box

multidimensional-array