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.