How can I find all the rectangles that connect the regions in the bitmap?

Question

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

I have a 2d array that stores my non-transition tiles.

Now I want to implement a lightweight engine, but this engine needs shadow hulls.

So, I need an algorithm that will create these shadow wrappers.

I need a set of rectangles that connect the intransitive parts of the array (cells that have 1 s)
For example:

Black tile 1 s; I need to find a set of red rectangles that completely cover them.

Answer 1

After further thought, I came up with a faster solution:

• Create an immutable Range structure with StartX , StartY and EndY properties.

• Maintain a sparse array of current Range s, with a length equal to the height of the image, and one variable with a currentRange value of zero. This array will contain a range, if any, that starts with each Y coordinate

• For each column

  • Clear currentRange

  • For each cell in the column:

    • If currentRange does not exist, or is, but it ended before this cell (if currentRange.EndY <= y ), set currentRange to the y'th element in the ranges array.
      That way, currentRange will always refer to the range containing the current cell, or null if the current cell is not in the range.

    • If current cell 1 :

      • If we are in a range, we do nothing - the range continues in the next column.

      • If we are not in a range, scroll through the column until we click on 0 or the end of the column, and then create a new range extending from 1 , which we just found until the end of the loop.
        Then move on to the next if (since the current cell is now 0 or the end of the column, and we are not in the range)
        If you click on an existing range while moving forward to create a new range, you can either stop the new range, or let the existing range continue to work lower (best for fuzzy edges), or close the existing range (see below), and let the new range stretches down to move from an existing range.

    • If current cell is 0 :
      • If we are in a range, close the range:
        • Returns a new rectangle extending from the beginning of the range X and Y to the current Y and the end of the range X.
        • Clear range from array of active ranges.

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

You can also rotate this algorithm and scan rows, not columns (so that the ranges will be stretched down rather than right), which will be O(x) in the repository.

Here is the 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); } } } } } 

Answer 2

Try something like this:

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

• For each point in this list:

  • Scroll down the y axis to this point until you click on the unwanted point (a 0 )
  • Move along the X axis until you click on the X coordinate, which has 0 for any value of Y between the point and the final Y coordinate obtained from step 1.
  • Add the rectangle you just found to the list of rectangles
  • Remove each point of the rectangle from the source list.

This is probably not the fastest way to do this, but it should work.