Merge smaller rectangles into larger ones

Question

I have a problem when I need to combine small squares into large rectangles. Let's say I have a 2D grid filled with random 1 and 0:

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 

1 represent areas that are filled, and I draw them to show the way down the line as squares. However, for this problem, I need to first match them with the rectangles. In the show example, 1 in the upper left corner →

 1 1 

can be connected to a rectangle.

I think this should be enough to explain what I need. However, it is preferred that a particular square is not used in more than one rectangle. Also, this should not be the best case with the fewest rectangles, just the best case with fewer rectangles. 1x1 rectangles are also allowed, which will facilitate the task.

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

If you want to know the cause of this problem, I’m working on a level creator for the game I’m working on, and I want to reduce the number of vertices. I thought I would start with squares because they will be simple, but even that scares my mind.

Thanks for taking the time to read!

Answer 1

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 connect horizontally adjacent squares, then go through the grid vertically and connect vertically adjacent squares.

Consider:

H = piece of horizontal rectangle

V = piece of vertical rectangle

Your original example:

  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 

will turn into:

 V 0 HH 0 V 0 HHH 0 V 0 HH 0 V 0 HH 0 0 1 0 0 

This approach is not optimal, but it will turn squares into rectangles, if possible with a 2D grid.

Answer 2

I use 2 steps to reduce the number of colliders in my game. Merge horizontally sequential types, then merge vertical types with the same width.

The code works, but it works ~

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