从一个2D的瓷砖数组中获取矩形。

Question

I basically want to convert this input:

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建议的那样，另一个答案可能是反过来工作，提供矩形并获得数组作为输出，我将尝试让它起作用并将其作为答案放入（如果没有人首先让它起作用），但我希望它可以用第一种方式完成。

- Alxs24

---

这是一个有趣的问题 - 如果可能的话，反过来做会更容易（提供矩形并获得输出），如果你只需要单向或双向都可以。此外，如果您想处理带有空洞的输入（例如将 tiles[0][1] 设置为 0 - 有多个矩形布局可供选择），这可能变得非常复杂。 - Marty

也许只需编辑此问题以指出您希望它反过来工作（尽管此评论线程将实现相同的效果）。 - Marty

正如@Marty所指出的那样，原问题需要澄清当有多个答案时该怎么办。在您给出的示例中已经存在这种情况，我们可以有(x=5，y=1，w=1，h=3)而不是您给出的答案。 - wookie919

我还会补充一下，重叠的矩形是否可以接受 - 我认为不行。 - Marty

在我的情况下，矩形布局并不重要，因为我只是将它们用于AABB碰撞检测，无论哪种方式都可以工作，因此任何填充数组中的1的矩形组合对我来说都可以。 - Alxs24

Answer 1

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

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

- Marty

---

哦，天啊，你太快了！这个函数运行得如此完美，以至于我现在不得不扔掉我自己写的那个哈哈。不过我还是会等待第一个问题的答案。 - Alxs24

Answer 2

这不是一个非常困难的问题，但确实是一个有趣的问题。您可以编写一个函数，给定矩形开始的坐标，该函数可以调用一个函数来更改网格并将包含在矩形中的元素清零。然后只需要迭代网格即可。以下是类似于C语言的伪代码：

var grid = {{0, 0, 0....}}
var output = {}

function examine_rectangle(x, y) {
    var w = 1
    var h = 1

    while (grid[y][x + w] == 1) {
        w += 1
    }

    var i = 0

    while (grid[y + h][x + i] == 1) {
        if (i == w - 1) {
            i = 0
            h += 1
        } else {
            i += 1
        }
    }

    output.push({x, y, w, h})

    clean_rectangle(x, y, w, h)
}

function clean_rectangle(x, y, w, h) {
    var i = 0

    while (i < w) i += 1) {
        var j = 0

        while (j < h) {
            grid[y + j][x + i] = 0
            j += 1
        }

        i += 1
    }
}

var x = 0

while (x < grid[0].size()) {
    var y = 0

    while(y < grid.size()) {
        if (grid[y][x] == 1) {
            examine_rectangle(x, y)
        }

        y += 1
    }

    x += 1
}

// yey! now we have got our answer in the output array

- Fors