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

Question

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

我有一个2D数组，其中存储着我不能行走的瓦片。

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

因此，我需要一个算法来创建这些阴影壳。

我需要一组矩形来包围数组中不可行走的部分（即具有1的单元格）。

例如：

黑色瓦片是1；我需要找到完全包围它们的红色矩形集。

- EnemyArea

---

你是用什么作为计算基础？你有哪些数据？ - SLaks

从像这样的2D数组开始：http://makerland.de/array.txt - EnemyArea

这个问题有点太宽泛了，你已经做了什么，尝试了什么，有没有示例代码？ - thedaian

这个问题并不太宽泛，它是一个简单、明确定义的问题。但是，我不知道该如何解决它。 - SLaks

感觉你可以从一个随机未分配的点开始，“拖动”一个方向（即x轴）直到找到“墙壁”，然后在垂直方向（即y轴）上“拖动”以找到另一个“墙壁”，称之为矩形。对于另一个未分配的点重复此过程。可能有更好的解决方案，因为这可能会产生许多不必要的矩形。 - Owen

这是一个有趣的问题。如果我不在工作，我会试着解决它 :) - Alastair Pitts

Answer 1

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

1. 创建一个不可变的 Range 结构体，具有 StartX、StartY 和 EndY 属性。

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

3. 对于每一列：

   1. 清除 currentRange。

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

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

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

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

         2. 如果我们不在范围内，则向下循环该列，直到遇到 0 或列的结尾，然后创建一个新范围，从刚找到的 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);
                }
            }
        }
    }
}

- SLaks

Answer 2

尝试类似以下的方法：

1. 创建一个包含每个所需点的列表。(在您的情况下，是每个 1 的坐标)

2. 对于此列表中的每个点：

   1. 从该点沿 Y 轴向下循环，直到遇到不需要的点 (即 0)
   2. 沿 X 轴向右循环，直到您找到具有 0 的 X 坐标，该坐标位于从步骤 1 中获取的结束 Y 坐标与该点之间的任何 Y 值。
   3. 将刚刚找到的矩形添加到矩形列表中
   4. 从原始列表中删除矩形中的每个点。

这可能不是最快的方法，但它应该有效。

- SLaks