Looking for an algorithm to divide a grid into sub-rectangles.

Given an MxN grid that contains a number of predefined sub-rectangles (blocked areas). How would you divide the grid into a min-set of sub-rectangles that don't overlap each other. The new rectangles will represent open areas.

Thanks

 

What do you mean by 'open-areas'?

Are you asking how to scan a region, such as a walkable region for a pathing grid, where open areas are those spaces that are walkable. Implying closed regions are unwalkable?

Do you have a algorithm/method to test "openness" of a sub-region?

Like something like this:

Where the red blocks are 'unwalkable/closed', and white are 'open/walkable'?

And we joined nodes to be larger rectangular areas (as shown by some shade of blue/purple)?

Note... you're going to have to define things like "min-set" and "open" and what not.

Example, in this image above we could easily rotate the rect in the lower left, making a 2x3 rect, removing the dark blue small rect above it, and making a new 2x2 square to the right of it. And still have the same number of over-all rects.

So... what would "min" mean? Min scanning from a left-right direction? Min from a maximum size rect first preference? Min from a small size rect first preference? From some other undefined meaning of 'min' that I could not guess at?

...

Personally, instead of trying to run down some graph-theory rabbit hole.

How I usually deal with these sorts of problems is that I draw on paper what it is I'm trying to reduce.

Then I attempt to do it in a more human method... just filling in the regions in a manner that I think works (like I did here in the pic I posted).

I keep doing this looking for a pattern that I keep using to attempt to fill the job. And iterate on that pattern until I have a specific rule set that I keep using... rather than a gut feeling. Like maybe I scan from upper-left to lower right just filling block by block until I hit a wall and I then walk that rect.

Once I have this human algorithm... I just translate it to computer.

Then once in computer form I can sometimes see optimizations in loops or what not which allow me to iterate further on the algorithm.

I don't do this for long... just as a proof of concept. If it works, then YAY, no need to study for hours. If not I then research based on my experience gathered (such as how I noticed by simply rotating a rect I can create a unique grid with the same number of rects... thus creating a proof that 'min' is nebulous).

 

I already know what areas are walk-able. that's the easy part. I didn't ask for a scanning algorithm.

As for " min-set of sub-rectangles". I'm looking for the smallest number of rectangles that will fill the open areas without overlap. This means that correct solution contains rectangles that are as large as possible and fewest in number.

With that said, there are obviously many solutions that will result in 7 rectangles ( as per your grid). I only need one of them. Your second graph is what I'm looking for.

I've tried to develop an algorithm a few times on graph paper, but I haven't really figured it out. I was just wondering if anyone has seen something like this or has any ideas.


Thanks.

 

The solution I have so far is to start with a large rectangle and check for overlaps. If it doesn't overlap, flag all the squares it fills, and continue searching. When the grid search is complete, loop over the grid again with a smaller rectangle.

The problem is how to reduce the size of the rectangle on each iteration. I suppose I could do it many different ways and then pick the solution with the smallest number of rectangles.

I'll probably have to scan the grid many different ways on each iteration.
Scan method 1 Reduce width only
Scan method 2. Reduce height only.
Scan method 3. Reduce height and width