Combine smaller rectangles into larger ones

Question

I have a problem where I need to merge small squares into larger rectangles. Say I have a 2D grid, filled with random 1's and 0's:

1 0 1 1 0
1 0 1 1 1
0 1 0 1 1
0 1 0 1 1
0 0 1 0 0

The 1's represent areas that are filled, and I draw them to screen way down the line as squares. However, for this problem, I need to match them up into rectangles first. In the example show, the 1's in the top left corner ->

1
1

can be joined into a rectangle.

I think that should be sufficient to explain what I need. It is preferable, however, that a particular square not be used in more than one rectangle. Also, it does not have to be the best case with the least number of rectangles, just a better case with fewer rectangles. 1x1 rectangles are also allowed were it would make things easier.

Any insight into where I could start, or even a solution will be appreciated.

If you want to know the reason behind this problem, I am working on a level builder for a game I am working on, and I want to reduce my vertex count. I thought I'd start with squares because they would be simple, but even this is boggling my mind.

Thank you for taking time to read!

Answer 1

I'm using 2 steps to reduce the numbers of colliders in my game. Merging horizontally consecutive types, then merging vertically types that have the same width.

The code is a work in progress, but it seems to be working~

public class Tiles
{
    public char Type { get; set; }
    public int X { get; set; }
    public int Y { get; set; }
    public int Width { get; set; }
    public int Height { get; set; }

    public override string ToString()
    {
        return $@"({X}, {Y}, {Width}, {Height}) '{Type}'";
    }
}

public class TilesFromStrings
{
    private List<Tiles> Result = new List<Tiles>();

    public IEnumerable<Tiles> Create(params string[] lines)
    {
        Result.Clear();

        CreateMergedHorizontalTiles(lines);
        MergeVerticallyTilesWithSameWidth();

        return Result.Where(f => f.Height > 0);
    }

    private void MergeVerticallyTilesWithSameWidth()
    {
        foreach (var current in Result)
        {
            foreach (var other in Result)
            {
                if (other.Y + other.Height == current.Y
                        && other.X == current.X
                        && other.Height > 0
                        && current.Height > 0)
                {
                    if (other.Type == current.Type)
                    {
                        if (other.Width == current.Width)
                        {
                            current.Height--;
                            current.Y++;
                            other.Height++;
                            break;
                        }
                    }
                }
            }
        }
    }

    private void CreateMergedHorizontalTiles(string[] tiles)
    {
        Tiles currentRect = null;
        var lastColumnIndex = tiles[0].Length - 1;
        for (int rowIndex = 0; rowIndex < tiles.Length; rowIndex++)
        {
            for (int columnIndex = 0; columnIndex < tiles[rowIndex].Length; columnIndex++)
            {
                var currentType = tiles[rowIndex][columnIndex];

                if (columnIndex == 0)
                {
                    currentRect = new Tiles
                    {
                        X = columnIndex + 1,
                        Y = rowIndex + 1,
                        Width = 1,
                        Height = 1,
                        Type = currentType
                    };

                    continue;
                }

                if (columnIndex == lastColumnIndex)
                {
                    if (currentRect.Type == currentType)
                    {
                        Result.Add(currentRect);
                        currentRect.Width++;
                    }
                    else
                    {
                        Result.Add(currentRect);
                        currentRect = new Tiles
                        {
                            X = columnIndex + 1,
                            Y = rowIndex + 1,
                            Width = 1,
                            Height = 1,
                            Type = currentType
                        };
                        Result.Add(currentRect);
                    }

                    continue;
                }

                if (currentRect.Type == currentType)
                {
                    currentRect.Width++;
                }
                else
                {
                    Result.Add(currentRect);
                    currentRect = new Tiles
                    {
                        X = columnIndex + 1,
                        Y = rowIndex + 1,
                        Width = 1,
                        Height = 1,
                        Type = currentType
                    };
                }
            }
        }
    }
}

Answer 2

A simple approach would be to look for adjacent squares and turn them into rectangles. To do this first go horizontally through the grid and join together horizontally adjacent squares, then go through the grid vertically and join vertically adjacent squares.

Consider:

H = piece of horizontal rectangle

V = piece of vertical rectangle

Your original example of:

 1 0 1 1 0
 1 0 1 1 1
 0 1 0 1 1
 0 1 0 1 1
 0 0 1 0 0

would turn into:

V 0 H H 0
V 0 H H H
0 V 0 H H
0 V 0 H H
0 0 1 0 0

This approach is not optimal, but it will turn squares into rectangles if it is possible to do so given the 2D grid.