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.