7

我有一个问题：我的图块引擎需要一个算法。

我有一个二维数组来存储我的不可行走的瓷砖。

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

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

我需要一组矩形来绑定数组的不可行走部分（具有1s 的单元格）
例如：

http://makerland.de/Zerlegt.png

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

4

2 回答 2

2

尝试这样的事情：

  1. 创建一个包含每个所需点的列表。（在你的情况下，每个坐标1）

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

    1. 从该点沿 Y 轴循环，直到遇到不想要的点 (a 0)
    2. 沿着 X 轴向右循环，直到您碰到一个 X 坐标，该 X 坐标0在该点和您从步骤 1 获得的结束 Y 坐标之间具有任意 Y 值。
    3. 将刚刚找到的矩形添加到矩形列表中
    4. 从原始列表中删除矩形中的每个点。

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

于 2011-07-22T00:52:12.063 回答
2

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

  1. 使用、和属性创建不可变Range结构。StartXStartYEndY

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

  3. 对于每一列，

    1. 清除currentRange

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

      1. 如果没有 currentRange，或者如果有但它在此单元格之前结束（如果currentRange.EndY <= y），则将 currentRange 设置为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);
                }
            }
        }
    }
}
于 2011-07-24T18:56:13.673 回答