algorithm - 从二维图 block 数组中获取矩形

Question

我基本上想转换这个输入:

var tiles:Array = new Array();

tiles[0] = [1, 1, 1, 1, 0, 0, 0, 0, 0, 0];
tiles[1] = [1, 1, 1, 1, 0, 1, 1, 1, 0, 0];
tiles[2] = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0];
tiles[3] = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0];
tiles[4] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
tiles[5] = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0];
tiles[6] = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1];
tiles[7] = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1];
tiles[8] = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1];
tiles[9] = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1];

到此输出(矩形向量):

[
    (x=0, y=0, w=4, h=2),
    (x=5, y=1, w=3, h=1),
    (x=5, y=2, w=1, h=2),
    (x=2, y=5, w=1, h=1),
    (x=5, y=6, w=5, h=4)
]

它也不能是重叠的矩形，它可以是任何布局，而不仅仅是我给的那个。

我一直在寻找 as3 或算法的代码示例，但它们总是使用其他编程语言或实现起来很复杂，所以我希望这里的人已经遇到了同样的问题。

编辑:正如@Marty所建议的那样，另一个答案可能是相反的，提供矩形并将数组作为输出，我会尝试让它工作并将其作为答案(如果没有人首先让它工作) 但我希望它可以通过第一种方式完成。

Answer 1

我会尝试解决您最初的问题，但现在如果您想将一些输入矩形转换为二维数组，您可以尝试我制作的这个函数:

function rectanglesToArray(input:Vector.<Rectangle>):Array
{
    var r:Rectangle;
    var gwidth:int = 0;
    var gheight:int = 0;

    // Determine the width and height of the grid.
    for each(r in input)
    {
        gwidth = Math.max(r.x + r.width, gwidth);
        gheight = Math.max(r.y + r.height, gheight);
    }


    // Define empty cells.
    var output:Array = [];
    for(var i:int = 0; i < gheight; i++)
    {
        output[i] = [];

        for(var j:int = 0; j < gwidth; j++)
            output[i].push(0);
    }

    // Define filled rectangles.
    for each(r in input)
    {
        for(var column:int = r.x; column < r.x + r.width; column++)
        {
            for(var row:int = r.y; row < r.y + r.height; row++)
            {
                output[row][column] = 1;
            }
        }
    }

    return output;
}

通过一个小演示:

var result:Array = rectanglesToArray(new <Rectangle>[
    new Rectangle(0, 0, 4, 2),
    new Rectangle(5, 1, 3, 1),
    new Rectangle(5, 2, 1, 2),
    new Rectangle(2, 5, 1, 1),
    new Rectangle(5, 6, 5, 4)
]);

trace(result.join("\n"));

给出输出:

1,1,1,1,0,0,0,0,0,0
1,1,1,1,0,1,1,1,0,0
0,0,0,0,0,1,0,0,0,0
0,0,0,0,0,1,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,0,0,0,1,1,1,1,1
0,0,0,0,0,1,1,1,1,1
0,0,0,0,0,1,1,1,1,1
0,0,0,0,0,1,1,1,1,1