How can I find all rectangles that bound regions in a bitmap?

Question

I have a problem: I need an algorithm for my tile engine.

I have an 2d-array which stores my un-walkable tiles.

Now I want to implement a light engine, but this engine need shadow-hulls.

So I need an algorithm which will create these shadow-hulls.

I need a set of rectangles that bound the un-walkable portions of the array (the cells that have 1s)
For example:

The black tile are 1s; I need to find the set of red rectangles that fully enclose them.

Explant

What are you calculating them from? What data do you have? – Embranchment

from an 2d-array like that: makerland.de/array.txt – Explant

This question is a bit too broad, what have you done already, what have you tried, do you have any example code? – Fulvia

@thedaian: The question is not too broad; it's a simple, well-defined problem. However, I have no idea how to do it. – Embranchment

Feels like you could start at a random unassigned point, 'drag' in one direction (i.e. x-axis) until you find a 'wall', then 'drag' in the perpendicular direction (so y-axis) to find another 'wall', call that a rectangle. Repeat for another unassigned point. Probably better solutions out there though, as this is likely to come up with a lot of unnecessary rects. – Backcourt

This is an interesting question. If I wasn't at work i'd have a go at this :) – Rishi

Answer 1

After further thought, I've come up with a faster solution:

1. Create an immutable Range struct with StartX, StartY, and EndY properties.

2. Maintain a sparse array of current Ranges, with length equal to the height of the image, and a single nullable currentRange variable. This array will contain the range, if any, that starts at each Y coordinate

3. For each column,

   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.
         Thus, currentRange will always refer to the range that contains the current cell, or null if the current cell is not in a range.

      2. If the current cell is 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.
            Then, proceed to the next if (since the current cell is now 0 or the end of the column, and we're not in a range)
            If you hit an existing range as you loop ahead to create the new range, you can either stop the new range and let the existing range continue below it (best for fuzzy edges), or close the existing range (see below) and let the new range stretch downwards to take over from the existing range.

      3. 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.

This algorithm is O(x * y) in computation and O(y) in space. I believe that this is the fastest solution to the problem.

You can also rotate this algorithm and scan rows rather than columns (so that ranges would be stretched downwards rather than rightwards), which will be O(x) in storage.

Here is a C# implementation:

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);
                }
            }
        }
    }
}

Embranchment

Answer 2

Try something like this:

1. Create a list containing every desired point. (In your case, the coordinates of every 1)

2. For each point in this list:

   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.

This probably isn't the fastest way to do this, but it should work.

Embranchment