如何在位图中找到所有限定区域的矩形？

Question

我有一个问题:我需要一个用于我的瓦片引擎的算法。

我有一个2D数组，用来存储我无法行走的瓷砖。

现在我想实现一个灯光引擎，但是这个引擎需要阴影外壳。

所以我需要一个算法来创建这些阴影外壳。

我需要一组矩形来限定数组中不能遍历的部分(具有1s的单元格)

例如：

​

​

黑色的磁贴是1；我需要找到一组完全包围它们的红色矩形。

Answer 1

经过进一步的思考，我想出了一个更快的解决方案：

1. 创建一个不可变的Range结构，使用StartX、StartY和EndY创建一个由当前Range组成的稀疏数组(长度等于图像的高度)和一个可以为空的currentRange变量。此数组将包含从每个Y coordinate
2. For每列

开始的范围(如果有

1. Clear `currentRange`
2. For each cell in the column:

    1. If there is no currentRange, or if there is but it ended before this cell (if `currentRange.EndY <= y`), set currentRange to the `y`'th element in the ranges array.

因此，currentRange将始终引用包含当前单元格的区域，如果当前单元格不在某个区域中，则为null。

2.如果当前单元格为1：

然后，转到下一个

        1. If we're in a range, do nothing – the range is continuing into the next column.
        2. If we're not in a range, loop down the column until we hit a `0` or the end of a column, then create a new range stretching from the `1` we just found until the end of the loop.

(因为当前单元格现在是0或列的结尾，而我们不在某个范围内)

如果在向前循环以创建新范围时遇到现有范围，则可以停止新范围并让现有范围在其下方继续(最适合于模糊边)，或者关闭现有范围(请参见下文)并让新范围向下延伸以接管现有范围。

​

    1. If the current cell is `0`:  
        1. If we're in a range, close the range: 
            1. Return a new rectangle stretching from the range's start X and Y to the current Y and the range's end X.
            2. Clear the range from the array of active ranges.

​

​

​

​

该算法在计算上是O(x * y)的，在空间上是O(y)的。我相信这是解决问题的最快方法。

您还可以旋转此算法并扫描行而不是列(这样范围将向下而不是向右延伸)，这将在存储中为O(x)。

下面是一个C#实现：

class BoxFinder {
    class Range {
        public Range(int startX, int startY, int endY) {
            StartX = startX;
            StartY = startY;
            EndY = endY;
        }

        public int StartX { get; private set; }
        public int StartY { get; private set; }
        public int EndY { get; private set; }
    }
    public BoxFinder(int[,] data) {
        Data = data;
        Width = data.GetLength(0);
        Height = data.GetLength(1);
        ranges = new Range[Height];
    }

    public int[,] Data { get; private set; }
    public int Width { get; private set; }
    public int Height { get; private set; }

    private Range[] ranges;
    public IEnumerable<Rectangle> GetBoxes() {
        for (int x = 0; x < Width; x++) {
            Range currentRange = null;
            for (int y = 0; y < Height; y++) {
                Func<Range, Rectangle> CloseRange = r => {
                    currentRange = null;
                    ranges[r.StartY] = null;
                    return new Rectangle(
                        r.StartY,
                        r.StartX,
                        x - r.StartX,
                        r.EndY - r.StartY
                    );
                };

                if (currentRange == null || currentRange.EndY <= y)
                    currentRange = ranges[y];

                if (Data[x, y] == 1) {
                    if (currentRange == null) {
                        int startY = y;
                        for (; y < Height && Data[x, y] == 1; y++) {
                            if (ranges[y] != null)
                                yield return CloseRange(ranges[y]);
                            //If there are fuzzy edges, break; instead
                        }
                        ranges[startY] = new Range(x, startY, y);
                        if (y == Height)
                            continue;
                        //Otherwise, continue to the next if in case a previous range just ended
                    }
                }
                //No else; we can get here after creating a range
                if(Data[x, y] == 0) {
                    if (currentRange != null)
                        yield return CloseRange(currentRange);
                }
            }
        }
    }
}

Answer 2

尝试如下所示：

1. 创建一个包含每个所需点的列表。(在您的示例中，此列表中的每个点的坐标为：

1)

1. For

1. Loop down the Y axis from this point until you hit an undesired point (a `0`)
2. Loop right along the X axis until you hit an X coordinate which has a `0` at any Y value between the point and the ending Y coordinate you got from step 1.
3. Add the rectangle you just found to the list of rectangles
4. Remove every point in the rectangle from the original list.

​

这可能不是最快的方法，但它应该可以工作。