Hi. I'm currently trying to find a solution to a grid filling problem. Unfortunately, i'm having trouble imagining the implementation.

I will explain. In a 2D grid, a cell can be filled or not. I need to retrieve the total number of contiguous rectangles that can be formed by the filled regions. I'm fairly sure what i'm looking after have a name, but it's hard to google it without the proper name.
I have attached an image of what i mean at the end of this post.

Currently, i have a double for loop for each rows and each columns. I remember the amount of "widths" of consecutive filled cell of the last row and if the current row have the same "widths" at the same place, i add one to that width height. But this is where i'm stuck, i can't find the rest of the logic.

// This function will calculate the number of void zone and store it in mVoidZones
void MapManager::CalculateVoidZones()
{
    // array of rectangle (X, Y, W, H).
    mVoidZones.clear();

    std::vector<SDL_Point> lastcorners;
    std::vector<int> widths;
    std::vector<int> heights;

    // scan a col. 
    for(int col = 0; col < mInfo->GetCol(); col++)
    {
        // remember the current width a consecutive void state.
        int width = 0;
        SDL_Point lastcorner = SDL_Point();
        lastcorner.x = -1;
        lastcorner.y = -1;

        // scan a row.
        for(int row = 0; row < mInfo->GetRow(); row++)
        {
            // fetch if the cell is "filled"
            if(GetTile(row, col)->IsState(STATE_TILE_VOID))
            {
                // add a corner
                if(lastcorner.x == -1 && lastcorner.y == -1)
                {
                    lastcorner.x = col;
                    lastcorner.y = row;
                    width = 1;
                }

                // increment the current width
                else if (lastcorner.x == col - 1)
                    width++;
            }

            // a gap is found. Close the current width.
            else if(width > 0)
            {
                lastcorners.push_back(lastcorner);
                widths.push_back(width);

                lastcorner.x = -1;
                lastcorner.y = -1;
                width = 0;
            }
        }
    }

    // TODO this function is incomplete.
    // It is missing the "corner" comparison, then adding the height 
    // then creating the rectangle and pushing it to mVoidZones.
}

Take note that the grid can be massively scrambled or even checkered, creating a huge number of small rectangles.

As always, thank you for your time. I will continue searching in the meantime.

Are rectangles the only type of shape that can be formed by the filled regions? Or can it be arbitrary shapes? If it's arbitrary shapes, do you skip those that aren't rectangles, or do you have to count the individual rectangular potions that make up the shape?

It's called shape vectorization or bitmap vectorization. You'll also have to handle the case where two rectangles touch.

Only the rectangles are interesting me.

This means a "star" shape composed of one 3x3 square and 1 filled cell on each side on the middle will be counted as 5 different rectangles. (the 3x3, and 4 1x1s).

0001000

0011100

0111110

0011100

0001000

It's called shape vectorization or bitmap vectorization. You'll also have to handle the case where two rectangles touch.

I've googled your answer, but what i found didn't seems related to my problem. I'll google more for the moment.

I finally figured out the algorithm i needed. Here is my solution, in case some one need it (in C++).

Please note that my solution will scan along the X axis all the way to the end before going to the next row. This is exactly how my game need it, but i feel the need to mention it.

The algorithm is not optimized. In my case, it did not need to be optimized.

//////////////////////////////////////////////////////////////////////////
// Calculate the rectangles that can exist in a grid.
std::vector<SDL_Rect> MapManager::CalculateVoidZones()
{
    std::vector<SDL_Point> corners;
    std::vector<SDL_Point> sizes;

    // Retrieve the maximum col and row. note that the col and row are already shrinked by 1.
    SDL_Point max = {mInfo->GetCol(), mInfo->GetRow()};

    // scan a col. Start from top left.
    for(int row = 0; row <= max.y; row++)
    {
        // remember the current width for consecutive void state.
        const short INVALID = -1;
        SDL_Point lastcorner = {INVALID, INVALID}; // invalid corner.
        int width = 0;

        // scan a col. go right.
        for(int col = 0; col <= max.x; col++)
        {
            bool lastcol = (col == mInfo->GetCol() && width > 0);
            bool addnewcorner = false, nonvoid = true;

            // if the cell is a void.
            if(GetTile(row, col)->IsState(STATE_TILE_VOID))
            {
                nonvoid = false;

                if(lastcorner.x == INVALID && lastcorner.y == INVALID)
                {
                    lastcorner.x = col;
                    lastcorner.y = row;
                }
                
                bool addwidth = lastcorner.x == (col - width);

                if (addwidth)
                    width++;

                if(!addwidth || lastcol)
                    addnewcorner = true;
            }

            if(addnewcorner || (nonvoid && width))
            {
                bool fit = false; // do the rectangle fit into a previous one?

                // loop through all existing corners
                for(unsigned int i = 0; i < corners.size(); i++)
                {
                    if(corners[i].x == lastcorner.x &&
                        corners[i].y == (lastcorner.y - sizes[i].y) &&
                        width == sizes[i].x)
                    {
                        // increase the height
                        sizes[i].y++;
                        fit = true;
                    }
                }

                if(!fit)
                {
                    corners.push_back(lastcorner);

                    SDL_Point size = SDL_Point();
                    size.x = width;
                    size.y = 1;
                    sizes.push_back(size);
                }

                // reset
                lastcorner.x = INVALID;
                lastcorner.y = INVALID;
                width = 0;
            }  
        }
    }

    // finally, create the rects
    std::vector<SDL_Rect> voidzones;
    if(corners.size() && corners.size() == sizes.size())
    {
        for(int i = corners.size(); i--;)
        {
            SDL_Point corner = corners[i];
            SDL_Point size = sizes[i];
            
            // mTw and mTh is the width and height of a tile, respectively.
            SDL_Rect rect = {corner.x * mTw,
                             corner.y * mTh,
                             size.x * mTw,
                             size.y * mTh};
            rects.push_back(rect);
        }
    }

    return voidzones;    
}

Have a good day.