如何查找位图中绑定区域的所有矩形？

Question

我有一个问题:我的瓷砖引擎需要一个算法.

我有一个2d阵列存储我的不可走路的瓷砖.

现在我想实现一个轻型引擎,但这个引擎需要暗影船体.

所以我需要一个能够创建这些影子船体的算法.

我需要一组矩形来绑定数组中不可走的部分(具有1s 的单元格)
例如:

黑色瓷砖是1s; 我需要找到完全包围它们的红色矩形集.

Answer 1

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

1. Range使用StartX、StartY和属性创建一个不可变结构EndY。

2. 维护一个当前 s 的稀疏数组Range，其长度等于图像的高度，以及一个可为空的 currentRange 变量。该数组将包含从每个 Y 坐标开始的范围（如果有）

3. 对于每一列，

   1. 清除currentRange

   2. 对于列中的每个单元格：

      1. 如果不存在 currentRange，或者存在但在此单元格之前结束 (if currentRange.EndY <= y)，则将 currentRange 设置为y范围数组中的第 ' 个元素。
         因此，currentRange将始终引用包含当前单元格的范围，或者null如果当前单元格不在范围内。

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

         1. 如果我们在一个范围内，则不执行任何操作 - 该范围将继续到下一列。

         2. 如果我们不在范围内，则向下循环该列，直到到达 a0或列的末尾，然后创建一个从1我们刚刚找到的 一直延伸到循环结束的新范围。
            然后，继续执行下一个 if （因为当前单元格现在0或列的末尾，并且我们不在范围内）
            如果您在向前循环创建新范围时遇到现有范围，您可以停止新范围并让现有范围继续低于它（最适合模糊边缘），或关闭现有范围（见下文）并让新范围向下延伸以接管现有范围。

      3. 如果当前单元格是0：
         1. 如果我们在一个范围内，则关闭该范围：
            1. 返回一个新的矩形，从范围的起始 X 和 Y 延伸到当前 Y 和范围的结束 X。
            2. 从活动范围数组中清除范围。

这个算法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);
                }
            }
        }
    }
}