CODEWITHSUNDEEP
algorithm
xdunder
xdunder

Reputation: 41

Algorithm to fill rectangle with small squares?

Given a rectangle with width and height, fill it with n squares (n is integer, also given), such that the squares cover as much of the rectangle's area as possible. The size of a single square should be returned.

Ideas?

Upvotes: 3

Views: 6675

Answers (4)

julien tonsuso
julien tonsuso

Reputation: 36

I know that question was a long time ago, but here is what i though :

you have n square you have a rectangle you want to know the size of the square to fill the rectangle

for example :

rectangle of 1280*720 filled with 100 squares. 
The surface is 1280*720=921600
1 square should have the surface of 921600/100 = 9216
so the square size is sqrt(9216)=96

In the end it would just be a function that return the result of this :

sqrt((width*height)/n)

Upvotes: 2

Sandy
Sandy

Reputation: 313

Here is my solution The idea is to go on a recursive loop Suppose u start with square_counter =0

While length and breath: // find the biggest possible square

Count1 = length/breath // take the floor

Square_counted += count1

New balance length = length - count1* breath

Now square with Max size possible wrt breath

Count2 = breath/length

Square_count += count2

Breath = breath - count* length

Upvotes: 0

Mikola
Mikola

Reputation: 9326

Assuming that all the squares are aligned and they are the same size, you can find this by binary searching on the side length of the square:

import math

def best_square(w, h, n):
    hi, lo = float(max(w, h)), 0.0
    while abs(hi - lo) > 0.000001:
        mid = (lo+hi)/2.0
        midval = math.floor(w / mid) * math.floor(h / mid)
        if midval >= n:
            lo = mid
        elif midval < n: 
            hi = mid
    return min(w/math.floor(w/lo), h/math.floor(h/lo))

Upvotes: 2

PengOne
PengOne

Reputation: 48398

The squares do not necessarily have to be oriented the same as the larger rectangle. These sorts of problems are known as packing problems, and finding optimal solutions is notoriously hard.

For an excellent treatment in the case when the larger shape into which the n squares are packed is a square, see Erich Friedman's paper Packing Unit Squares in Squares: A Survey and New Results

For example, Gödel was the first to publish on this subject. He found that a2+a+3+(a-1)√2 squares can be packed in a square of side a+1+1/√2 by placing a diagonal strip of squares at a 45 degree angle. For example,

Gödel's 5 square solution

And just for fun, I highly recommend you check out Erich's Packing Center.

Upvotes: 6

Related Questions