# Grids and vertices

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 :)

-
Do you specifically want that result (in your pic) or would 2 large horizontal rectangles above and below the red square with 2 small ones either side be ok? – George Duckett Apr 15 '13 at 9:27
It doesnt matter as long as total number of sub blocks is the smallest possible number. Also there will be more than 1 hole normally was just doing a minimalism example. – Chris Condy Apr 15 '13 at 9:31
There are multiple duplicate questions of this with different terminology. See for example stackoverflow.com/questions/5919298/… and the linked questions. Also on this site: gamedev.stackexchange.com/questions/50637/… – msell Apr 15 '13 at 9:32

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:

-

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 :)

-
that doesnt make much sense to me maybe you should illistrate it – GameDev-er Apr 15 '13 at 17:21
As GameDev-er said this doesnt make any sense, could you maybe rewrite or draw something – Chris Condy Apr 16 '13 at 0:18