Binary Array Reduce Map to Rectangles in C#

Question

Given the following c# array:

    const bool X = true, _ = false;
    bool[,] array = new bool[,] {
        { X, X, X, X, _, X, X, X, _, _ },
        { _, _, _, _, _, X, X, X, X, _ },
        { X, X, X, X, X, X, X, X, X, X },
        { X, X, X, X, X, X, X, X, X, X },
        { _, X, X, X, _, X, _, _, X, X },
        { _, X, X, X, _, X, X, _, X, X },
        { _, _, _, X, X, _, _, _, _, _ },
        { X, X, _, X, X, _, X, X, X, _ },
        { _, X, X, _, _, X, X, X, X, X },
        { _, _, X, X, _, _, X, X, X, X },
    };

Visually something like this:

Are there any existing methods for converting this to as few rectangular areas as possible?

A possible solution might be something like:

Ideally I'm looking for something that can produce a list of rectangles:

    public IEnumerable<Rectangle> ReduceMap(bool[,] map)
    {
        List<Rectangle> rects = new List<Rectangle>();
        int width = map.GetLength(0), height = map.GetLength(1);

        // Reduce
        // ....?

        return rects;
    }

The result of which would be something like:

    var output = new List<Rectangle>
    {
        new Rectangle(0, 0, 4, 1),
        new Rectangle(5, 0, 3, 2),
        new Rectangle(8, 1, 1, 1),
        new Rectangle(0, 2, 10, 2),
        // ... etc
    };

Speed is important too, the fewer rectangles the better, but finding a decent solution should not be overly computationally expensive.

Apologies if this has been answered before, if anyone has any idea where to look that would be great!

Answer 1

This is an interesting problem.
Have you seen the following article it provides good information on this topic and discusses different approaches to this problem (quadtree, morphological, graph): Rectangular decomposition of binary images
This comes from Ojdo's answer in this question Link
I would start looking there! Hope this helped.

Answer 2

This is the best I can come up with myself, if anyone can improve on this, I'd be happy to mark it as the answer.

This method uses multiple passes to union the array and seems to reduce the array pretty well, roughly in line with my diagrams above, although definitely not optimal.

I've created a fiddle for testing: https://dotnetfiddle.net/3iuIe6

using System;
using System.Collections.Generic;
using System.Drawing;

public class Program
{
    private const string pattern1 = @"
XXXX_XXX__
_____XXXX_
XXXXXXXXXX
XXXXXXXXXX
_XXX_X__XX
_XXX_XX_XX
___XX_____
XX_XX_XXX_
_XX__XXXXX
__XX__XXXX
";

    private const string pattern2 = @"
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
";

    private const string pattern3 = @"
X_XXXXXXXX
X_XXXXXXXX
X_XXXXXXXX
X_XXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXX_XX
XXXXXXX_XX
XXXXXXX_XX
XXXXXXX_XX
";

    private const string pattern4 = @"
X_XXXXXXXX
X_XX__XXXX
X_XXXXXXXX
X_XXXX__XX
XXXXX_XXXX
XXX__XXXXX
XXXX_XX_XX
XXX_XXX_XX
XXXXX_X_XX
XXX_XXX_XX
";

    private const string pattern5 = @"
XXXXXXXXXX
__XXXXXXXX
____XXXXXX
_____XXXXX
______XXXX
______XXXX
_____XXXXX
____XXXXXX
__XXXXXXXX
XXXXXXXXXX
";

    public static void Main()
    {
        bool[,] map = PatternTo2DArray(pattern1);
        //bool[,] map = PatternTo2DArray(pattern2);
        //bool[,] map = PatternTo2DArray(pattern3);
        //bool[,] map = PatternTo2DArray(pattern4);
        //bool[,] map = PatternTo2DArray(pattern5);

        var rects = ReduceMap(map);
        int index = 0;
        foreach (var rect in rects)
        {
            Console.WriteLine("{0}: {{ {1}, {2}, {3}, {4} }}", ((index + 1).ToString().PadLeft(1, '0')), rect.X, rect.Y, rect.Width, rect.Height);
            index++;
        }

        var total = DumpMap(map);
        Console.WriteLine("\r\nOptimised Map From: {0} to {1}", total, index);
    }

    public static IEnumerable<Rectangle> ReduceMap(bool[,] map)
    {
        int width = map.GetLength(0), height = map.GetLength(1);
        MapElement[,] bin = new MapElement[width, height];

        // Reduce
        // Step 1: Convert to map elements:
        for (int y = 0; y < height; y++)
            for (int x = 0; x < width; x++)
            {
                if (map[x, y])
                    bin[x, y] = new MapElement() { X = x, Y = y, Width = 1, Height = 1, Set = true };
            }

        // Step 2: Process the bin map and generate a collection of Rectangles horizontally     
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                // Only care about this if we are set.
                if (bin[x, y].Set)
                {
                    // Scan forward and link this tile with its following tiles
                    int xx = 0;
                    for (int xForward = x + 1; xForward < width; xForward++)
                    {
                        if (!bin[xForward, y].Set)
                            break;

                        // We can link this...
                        bin[xForward, y].Set = false;
                        bin[x, y].Width++;
                        xx++; // Skip over these tiles.
                    }

                    x += xx;
                }
            }
        }

        // Step 3: Process the bin map veritically and join any blocks that have equivalent blocks below them.
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                // Only care about this if we are set.
                if (bin[x, y].Set)
                {
                    // Scan down and link this tile with its following tiles
                    for (int yDown = y + 1; yDown < height; yDown++)
                    {
                        if (!bin[x, yDown].Set || bin[x, yDown].Width != bin[x, y].Width)  // We might be able to link this if it's the same size
                            break;

                        bin[x, yDown].Set = false;
                        bin[x, y].Height++;
                    }
                }
            }
        }

        // Step 4: Convert map to rectangles
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                // Only care about this if we are set.
                if (bin[x, y].Set)
                {
                    var b = bin[x, y];
                    yield return new Rectangle(b.X, b.Y, b.Width, b.Height);
                }
            }
        }
    }

    public static int DumpMap(bool[,] map)
    {
        Console.WriteLine("");
        var @out = 0;
        int width = map.GetLength(0), height = map.GetLength(1);
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                Console.Write(map[x, y] ? "X" : "_");
                @out++;
            }

            Console.WriteLine();
        }

        return @out;
    }

    public static int CountDataPoints(bool[,] map)
    {
        var @out = 0;
        int width = map.GetLength(0), height = map.GetLength(1);
        for (int y = 0; y < height; y++)
            for (int x = 0; x < width; x++)
                if (map[x, y])
                    @out++;

        return @out;
    }

    public static bool[,] PatternTo2DArray(string pattern)
    {
        var lines = new List<string>(pattern.Split('\n'));
        for (int i = lines.Count - 1; i > -1; i--)
        {
            string line = lines[i].TrimEnd('\r');
            if (line.Length == 0)
                lines.RemoveAt(i);
            else
                lines[i] = line;
        }

        var @out = new bool[lines[0].Length, lines.Count];
        for (int y = 0; y < lines.Count; y++)
        {
            string line = lines[y];
            for (int x = 0; x < line.Length; x++)
            {
                @out[x, y] = !(line[x] == '_');
            }
        }

        return @out;
    }

    internal struct MapElement
    {
        public int X;
        public int Y;
        public int Width;
        public int Height;
        public bool Set;
    }
}