Grids and vertices

Question

I have no idea what this is even called or even to start searching how to solve this problem. So figured I would post here for any information at all. Specially looking for already known solutions to this.

Say for example I have a grid - Aka one huge square which is easy to draw. If I punch holes in the grid how is it possible to find the biggest possible squares to fit within this grid. See the below picture:

Red is the punched out hole, and the squares is the squares that should be made.

As I said looking for any advice/solutions at all :)

Answer 1

First of all, you probably meant to subdivide into rectangles, not squares. The problem is generally not solvable with squares.

Now, if you want to split your region into rectangles given an arbitrary number of rectangular holes, then I have a strong feeling it's an NP-hard problem. Which means you probably don't want to solve the problem in the best possible manner, as long as you have a solution which is "good enough".

For example, for a single-hole shape the solution that you drawn in the picture looks to be optimal. You can similarly hand-draw the solutions to the cases when the hole is at the edge or in the corner.

Now, the simplest way to solve the multi-hole problem is the following:

1. Select one hole at random, and "solve" the tiling problem assuming that there are no other gaps.
2. Pick another hole. It belongs to one or more of the rectangles you constructed in step 1. So solve the tiling problem recursively for each of those rectangles.
3. Repeat steps 1 and 2 until all holes are accounted for.
4. If you want, as a final step you may want to see if any of the adjacent rectangles can be merged into a bigger rectangle.

See the illustration:

Answer 2

I don't know any c++ or opengl, but this is the basic concept you'd need:

x = minimum area you are calculating with

y = block

get area of all blocks

sequentially divide each block by x, like this (y/x, y2/x, y3/x, etc)

place the above in an array

Tell whatever's processing the code to print the largest number in the array

Done :)