CODEWITHSUNDEEP
algorithmmathuser-interfaceresizegeometry
user3388811
user3388811

Reputation: 358

Find an optimal n square size (same for each) to fit most part of rectangle container

Input

Rectangle area width and height, so we could calculate rectangle aspect/proportions.

N is the number of squares that we want to resize using the same size for each.

Output

Find the optimal squares size that would fit most part of our container. For example

containerWidth = 200;
containerHeight = 100;
n = 8;

In this case squaresSize should be 50 to fit most of rectangle area.

What i tried

I already tried to calculate container math area and then divide it to the number of squares to get each square area by taking a square root. But this is the ideal square size, so it douesn't respect each square place relative to container rectangle.

Real purpouse

I trying to make scallable user interface, that would draw as much square objects in rectangle container as it is possible.

Upvotes: 4

Views: 1767

Answers (2)

Timothy Shields
Timothy Shields

Reputation: 79461

Let S be the size of each square (width and height). Then you want to solve the optimization problem

  maximize S
subject to floor(Width / S) * floor(Height / S) >= n
           S >= 0

The feasible region is a range [0, S*], where S* is the optimal solution.

We know that S * S * n <= Width * Height for all feasible S; that is, S <= sqrt(Width * Height / n).

So you can simply binary search the range [0, sqrt(Width * Height / n)] for the largest value of S for which floor(Width / S) * floor(Height / S) >= n.

Once you have the optimal S*, you will place your squares into the container in a grid with floor(Width / S*) columns and floor(Height / S*) rows.

Upvotes: 1

MBo
MBo

Reputation: 80187

You have to solve inequality (find max value of a)

(Width div a) * (Height div a) >= n

where div is integer division with truncation (8 div 3 = 2)

Result depends monotonically on n, so get first approximation as 

a = Sqrt(W*H/n)

and find exact value with linear or binary search

Upvotes: 3

Related Questions