4
\$\begingroup\$

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:

Grid

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

\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$ Commented Apr 15, 2013 at 9:27
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Apr 15, 2013 at 9:31
  • 2
    \$\begingroup\$ 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/… \$\endgroup\$
    – msell
    Commented Apr 15, 2013 at 9:32

2 Answers 2

3
\$\begingroup\$

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:

enter image description here

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ that doesnt make much sense to me maybe you should illistrate it \$\endgroup\$
    – GameDev-er
    Commented Apr 15, 2013 at 17:21
  • \$\begingroup\$ As GameDev-er said this doesnt make any sense, could you maybe rewrite or draw something \$\endgroup\$ Commented Apr 16, 2013 at 0:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .