CODEWITHSUNDEEP
algorithmmath
aritomo
aritomo

Reputation:

Split square into small squares

I have big square. And I would like to split this square into small squares. I need all possible combinations. I know that there are infinity count of combinations but I have one limitation. I have fixed size for smallest square.

I can implement it using brute force. But it is too long.

Is any preferable algorithm for this task?

Thanks!

Upvotes: 4

Views: 8776

Answers (4)

Emilien Valat
Emilien Valat

Reputation: 11

I propose the following Python code to randomly split a big square (512x512) into smaller squares (min. 32x32).

import random 
import numpy as np

n = 16
cellSize = 32
smallSizes = [1,2,4,8]

def is_cell_available(grid, indexRow, indexCol):
    return not bool(grid[indexRow, indexCol])

def try_square_size(grid, indexRow, indexCol):
    smSizes = smallSizes.copy()
    while True:
        potentialSize = random.choice(smSizes)
        if indexRow + potentialSize <= n and indexCol + potentialSize <= n:
            if np.count_nonzero(grid[indexRow:indexRow+potentialSize, indexCol:indexCol+potentialSize])==0:
                return potentialSize
        else:
            smSizes.remove(potentialSize)

grid = np.zeros((n,n), np.uint8)
bigMat = np.zeros((n*cellSize,n*cellSize), np.uint8)

for indexRow in range(n):
    for indexCol in range(n):
        if is_cell_available(grid, indexRow, indexCol):
            blockSize = try_square_size(grid, indexRow, indexCol)
            val = random.randint(1,255)
            grid[indexRow:indexRow+blockSize, indexCol:indexCol+blockSize] = val
            bigMat[indexRow*cellSize:(indexRow+blockSize)*cellSize, indexCol*cellSize:(indexCol+blockSize)*cellSize] = val
        else:
            pass

Upvotes: 0

RMAAlmeida
RMAAlmeida

Reputation: 304

Well this problem only have solution if we made 2 assumptions (otherwise there is infine combinations)

1) the smalest square has a fixed size
2) the way to cut the big square is also fixed, as if you put the square into a grid which lines are separated by the size of the small square.

There is also an third assumption that would make the problem a bit easier

3) The big square has side K-times bigger than the small square. With K being an integer.

If both assumptions are true we can proceed:

Find the number of N (N beign integer) smallest squares: squares with size N*small-size

 if ((big-size % N*small-size)==0)
    Number += (big-size / N*small-size)^2
 else
    Number += ((big-size / N*small-size)^2) * (big-size % N*small-size)

The * (big-size % Nsmall-size) in the else condition is there becouse if the bigsquare isn't divided by N, when "griding" the big square with gid-width of N, we will have an "fraction part" left. This way we can start dividing again (griding again) but with an offset of 1, 2 or N small steps. The amount of steps is (big-size % Nsmall-size).

Again, these steps only hold true if the 3 assumptions were took.

Upvotes: 1

Eoin Campbell
Eoin Campbell

Reputation: 44278

My math is a bit fuzzy but if you have a square (n^2), then you have the length of one side (n).

From n you can calculate all the factors for that number, and use them as the sides for the smaller squares...

E.g.

n^2 = 44100
n = 210

Factors of n = x=2,x=3,x=5,x=7, x= ... and so on.

So you smaller squares for each factor are

x=2 : x^2 = 4 : 44100 / 4 = 11025 small squares
x=3 : x^2 = 9 : 44100 / 9 = 4900 small squares
x=5 : x^2 = 25 : 44100 / 25 = 1764 small squares
x=7 : x^2 = 49 : 44100 / 49 = 900 small squares

and so on

Upvotes: 0

Dan
Dan

Reputation: 1161

There are no "infinite" combinations. In fact, the number may be large but is bounded. Moreover, if you need strict squares (width=height, as opposed to just rectangles) there are even less, since you have to divide the original square (of side L) by the same integers on both sides otherwise you'll be getting rectangles as well. If you're working with integers, I would recommend just dividing L by 2, 3, ... M (L/M = minimum inner square length).

Upvotes: 0

Related Questions