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.

Answer 1

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.