Prev: Faster image rotation
Next: Question: Is there a programming language that meets this criteria?
From: Daniel T. on 10 Apr 2010 09:00
Kai-Uwe Bux <jkherciueh(a)gmx.net> wrote:
> Daniel T. wrote:
>
> > struct Pair findBestFit(double masterAspectRatio, double
> > rectAspectRatio, int count)
> > {
> > struct Pair result = { 1, count };
> > while (result.columns * rectAspectRatio > masterAspectRatio) {
> > --result.columns;
> > result.rows = count / result.columns +
> > (count % result.columns ? 1 : 0);
> > }
> > return result;
> > }
> [...]
>
> Huh? The condition for the while loop does not depend on result.rows. Hence,
> the loop just searches for the maximal result.columns <=
> masterAspectRatio/rectAspectRatio. Hence something like
>
> result.columns = std::floor( masterAspectRatio/rectAspectRatio );
> result.rows = ...
>
> should do the same. However, I doubt that this is what you are looking for.

Actually yes, that is exactly what I was looking for. The first time I
implemented something like this, it was for lots of different sized
sub-rectangles (a full out 2D box packing algorithm,) but this time all
the sub-rectangles are the same size so all I need to do is figure out
how to arrange the sub-rectangles so they have (close to) the same
aspect ratio as the main rectangle.

An example of a time when I solved a harder problem in the past and that
clouded my judgement for this related but simpler problem.
From: Kai-Uwe Bux on 11 Apr 2010 17:56
Daniel T. wrote:

> Kai-Uwe Bux <jkherciueh(a)gmx.net> wrote:
>> Daniel T. wrote:
>>
>> > struct Pair findBestFit(double masterAspectRatio, double
>> > rectAspectRatio, int count)
>> > {
>> > struct Pair result = { 1, count };
>> > while (result.columns * rectAspectRatio > masterAspectRatio) {
>> > --result.columns;
>> > result.rows = count / result.columns +
>> > (count % result.columns ? 1 : 0);
>> > }
>> > return result;
>> > }
>> [...]
>>
>> Huh? The condition for the while loop does not depend on result.rows.
>> Hence, the loop just searches for the maximal result.columns <=
>> masterAspectRatio/rectAspectRatio. Hence something like
>>
>> result.columns = std::floor( masterAspectRatio/rectAspectRatio );
>> result.rows = ...
>>
>> should do the same. However, I doubt that this is what you are looking
>> for.
>
> Actually yes, that is exactly what I was looking for. The first time I
> implemented something like this, it was for lots of different sized
> sub-rectangles (a full out 2D box packing algorithm,) but this time all
> the sub-rectangles are the same size so all I need to do is figure out
> how to arrange the sub-rectangles so they have (close to) the same
> aspect ratio as the main rectangle.
>
> An example of a time when I solved a harder problem in the past and that
> clouded my judgement for this related but simpler problem.

I am glad that the code is a solution to your problem. However, I cannot
square the solution and the original problem description:

I have a number of rectangles of a particular aspect ratio and an
overall aspect ratio I would like to maintain. So I need to be able to
determine how many rows and columns I need to come closest to the target
ratio. I've solved this problem before, I remember using a binary search
between 1 row 'x' columns and 'x' rows 1 column, but I can't remember
exactly what I did.

So, when you have a total of 100 small rectangles, all squares (aspect
ration is 1.0) and the big rectangle has aspect ratio 1.1, then the solution
from above gives:

columns = floor( 1.1 / 1.0 ) = 1
rows = count / columns + ( 0 or 1 ) \approx 100

I would have expected something like

columns = 9
rows = 10

with 10 unused squares. Just out of curiosity: what am I missing?


Best

Kai-Uwe Bux
From: Daniel T. on 12 Apr 2010 09:43
Kai-Uwe Bux <jkherciueh(a)gmx.net> wrote:

> I am glad that the code is a solution to your problem. However, I cannot
> square the solution and the original problem description:
>
> I have a number of rectangles of a particular aspect ratio and an
> overall aspect ratio I would like to maintain. So I need to be able to
> determine how many rows and columns I need to come closest to the target
> ratio. I've solved this problem before, I remember using a binary search
> between 1 row 'x' columns and 'x' rows 1 column, but I can't remember
> exactly what I did.
>
> So, when you have a total of 100 small rectangles, all squares (aspect
> ration is 1.0) and the big rectangle has aspect ratio 1.1, then the solution
> from above gives:
>
> columns = floor( 1.1 / 1.0 ) = 1
> rows = count / columns + ( 0 or 1 ) \approx 100
>
> I would have expected something like
>
> columns = 9
> rows = 10
>
> with 10 unused squares. Just out of curiosity: what am I missing?

Damn you are right, the code worked for a specific set of numbers but
isn't working in general.

So here are some test cases:

struct Pair {
int columns;
int rows;
};

Pair findBestFit(double masterAspectRatio, double rectAspectRatio, int
count);

int main()
{
Pair out;
out = findBestFit(1.0, 1.0, 1);
assert(out.columns == 1 && out.rows == 1);
// this should be the result whenever count == 1, no matter what the
// aspect ratios are.

out = findBestFit(2.0, 1.0, 2);
assert(out.columns == 2 && out.rows == 1);

out = findBestFit(0.5, 1.0, 2);
assert(out.columns == 1 && out.rows == 2);

out = findBestFit(1.0, 1.0, 2);
assert(out.columns == 2 && out.rows == 1);
// if masterAspectRatio == rectAspectRatio:
// out.columns == sqrt(count) rounded up
// there's a clue here for how to solve the problem, I think.

out = findBestFit(1.0, 1.0, 3);
assert(out.columns == 2 && out.rows == 2);

out = findBestFit(1.0, 0.5, 3);
assert(out.columns == 3 && out.rows == 1);

out = findBestFit(1.0, 0.5, 4);
assert(out.columns == 4 && out.rows == 1);

out = findBestFit(2.0, 0.5, 4);
assert(out.columns == 4 && out.rows == 1);

out = findBestFit(0.75, 0.5, 4);
assert(out.columns == 3 && out.rows == 2);

out = findBestFit(0.5, 0.5, 4);
assert(out.columns == 2 && out.rows == 2);

out = findBestFit(0.125, 0.5, 4);
assert(out.columns == 1 && out.rows == 4);
}
From: Kai-Uwe Bux on 12 Apr 2010 16:02
Daniel T. wrote:

> Kai-Uwe Bux <jkherciueh(a)gmx.net> wrote:
>
>> I am glad that the code is a solution to your problem. However, I cannot
>> square the solution and the original problem description:
>>
>> I have a number of rectangles of a particular aspect ratio and an
>> overall aspect ratio I would like to maintain. So I need to be able to
>> determine how many rows and columns I need to come closest to the
>> target ratio. I've solved this problem before, I remember using a
>> binary search between 1 row 'x' columns and 'x' rows 1 column, but I
>> can't remember exactly what I did.
>>
>> So, when you have a total of 100 small rectangles, all squares (aspect
>> ration is 1.0) and the big rectangle has aspect ratio 1.1, then the
>> solution from above gives:
>>
>> columns = floor( 1.1 / 1.0 ) = 1
>> rows = count / columns + ( 0 or 1 ) \approx 100
>>
>> I would have expected something like
>>
>> columns = 9
>> rows = 10
>>
>> with 10 unused squares. Just out of curiosity: what am I missing?
>
> Damn you are right, the code worked for a specific set of numbers but
> isn't working in general.
>
> So here are some test cases:

I do not see the pattern :-(

> struct Pair {
> int columns;
> int rows;
> };
>
> Pair findBestFit(double masterAspectRatio, double rectAspectRatio, int
> count);
>
> int main()
> {
> Pair out;
> out = findBestFit(1.0, 1.0, 1);
> assert(out.columns == 1 && out.rows == 1);
> // this should be the result whenever count == 1, no matter what the
> // aspect ratios are.
>
> out = findBestFit(2.0, 1.0, 2);
> assert(out.columns == 2 && out.rows == 1);
>
> out = findBestFit(0.5, 1.0, 2);
> assert(out.columns == 1 && out.rows == 2);
>
> out = findBestFit(1.0, 1.0, 2);
> assert(out.columns == 2 && out.rows == 1);

Really? If you did columns=1 rows=1 (with an unused tile), the overall
aspect ration would be much better.

> // if masterAspectRatio == rectAspectRatio:
> // out.columns == sqrt(count) rounded up
> // there's a clue here for how to solve the problem, I think.
>
> out = findBestFit(1.0, 1.0, 3);
> assert(out.columns == 2 && out.rows == 2);
>
> out = findBestFit(1.0, 0.5, 3);
> assert(out.columns == 3 && out.rows == 1);

Why not columns = 2?

> out = findBestFit(1.0, 0.5, 4);
> assert(out.columns == 4 && out.rows == 1);

Again.

> out = findBestFit(2.0, 0.5, 4);
> assert(out.columns == 4 && out.rows == 1);
>
> out = findBestFit(0.75, 0.5, 4);
> assert(out.columns == 3 && out.rows == 2);

Ok, so columns _may_ be less than count. So why not use that option in the
previous cases?

Also: rows*columns may exceed count.

> out = findBestFit(0.5, 0.5, 4);
> assert(out.columns == 2 && out.rows == 2);
>
> out = findBestFit(0.125, 0.5, 4);
> assert(out.columns == 1 && out.rows == 4);
> }


As I said, I do not see the pattern; so I cannot propose a solution.

That said: from the original problem description (and to some extent from
the test cases), it appears that

columns / rows

should be a good approximation to

masterAspectRatio / tileAspectRatio


Now, the problem of finding rational best approximations to real numbers is
solved via continued fractions (google for "rational best approximation" and
"continued fractions"). Maybe, you can use that as at least as a building
block for the 2D tiling problem with uniform tiles.


Best

Kai-Uwe Bux
From: Daniel T. on 12 Apr 2010 19:56
Kai-Uwe Bux <jkherciueh(a)gmx.net> wrote:
> Daniel T. wrote:
> > Kai-Uwe Bux <jkherciueh(a)gmx.net> wrote:
> >
> > > I am glad that the code is a solution to your problem. However, I
> > > cannot square the solution and the original problem description:
> > >
> > > I have a number of rectangles of a particular aspect ratio and
> > > an overall aspect ratio I would like to maintain. So I need to
> > > be able to determine how many rows and columns I need to come
> > > closest to the target ratio. I've solved this problem before, I
> > > remember using a binary search between 1 row 'x' columns and 'x'
> > > rows 1 column, but I can't remember exactly what I did.
> > >
> > > So, when you have a total of 100 small rectangles, all squares
> > > (aspect ration is 1.0) and the big rectangle has aspect ratio 1.1,
> > > then the solution from above gives:
> > >
> > > columns = floor( 1.1 / 1.0 ) = 1
> > > rows = count / columns + ( 0 or 1 ) \approx 100
> > >
> > > I would have expected something like
> > >
> > > columns = 9
> > > rows = 10
> > >
> > > with 10 unused squares. Just out of curiosity: what am I missing?
> >
> > Damn you are right, the code worked for a specific set of numbers
> > but isn't working in general.
> >
> > So here are some test cases:
>
> I do not see the pattern :-(
>
> > struct Pair {
> > int columns;
> > int rows;
> > };
> >
> > Pair findBestFit(double masterAspectRatio, double rectAspectRatio, int
> > count);
> >
> > int main()
> > {
> > Pair out;
> > out = findBestFit(1.0, 1.0, 1);
> > assert(out.columns == 1 && out.rows == 1);
> > // this should be the result whenever count == 1, no matter what the
> > // aspect ratios are.
> >
> > out = findBestFit(2.0, 1.0, 2);
> > assert(out.columns == 2 && out.rows == 1);
> >
> > out = findBestFit(0.5, 1.0, 2);
> > assert(out.columns == 1 && out.rows == 2);
> >
> > out = findBestFit(1.0, 1.0, 2);
> > assert(out.columns == 2 && out.rows == 1);
>
> Really? If you did columns=1 rows=1 (with an unused tile), the overall
> aspect ration would be much better.

In all test cases, assert(rows * columns >= count);

I can't put two rectangles in a 1 x 1 matrix.

> > // if masterAspectRatio == rectAspectRatio:
> > // out.columns == sqrt(count) rounded up
> > // there's a clue here for how to solve the problem, I think.
> >
> > out = findBestFit(1.0, 1.0, 3);
> > assert(out.columns == 2 && out.rows == 2);
> >
> > out = findBestFit(1.0, 0.5, 3);
> > assert(out.columns == 3 && out.rows == 1);
>
> Why not columns = 2?

If columns == 2, then rows would have to equal 2. The aspect ratio of a
2 x 2 matrix where each cell has an aspect ratio of 0.5 would be 0.5.
Since there are 3 rectangles, that would mean that only 37.5% of the
master rect is filled. The aspect ratio of a 3 x 1 matrix would be 1.5
and the master rectangle would be 66.6% filled. The objective is to fill
the master rectangle as completely as possible with the given
sub-rectangles.

For example, let's say that each rectangle is 1 x 2 (giving an aspect
ratio of 0.5,) while the master rectangle can be either 3 x 3 or 4 x 4
(any value, as long as its aspect ratio is 1.)

Placing the 3 rectangles in a 3 x 1 matrix embedded in a 3 x 3 master
rectangle leaves 3 square units unoccupied, while putting 2 x 2 matrix
embedded in a 4 x 4 master rectangle would leave 10 square units
unoccupied.

> > out = findBestFit(1.0, 0.5, 4);
> > assert(out.columns == 4 && out.rows == 1);
>
> Again.
>
> > out = findBestFit(2.0, 0.5, 4);
> > assert(out.columns == 4 && out.rows == 1);
> >
> > out = findBestFit(0.75, 0.5, 4);
> > assert(out.columns == 3 && out.rows == 2);
>
> Ok, so columns _may_ be less than count. So why not use that option in the
> previous cases?
>
> Also: rows*columns may exceed count.
>
> > out = findBestFit(0.5, 0.5, 4);
> > assert(out.columns == 2 && out.rows == 2);
> >
> > out = findBestFit(0.125, 0.5, 4);
> > assert(out.columns == 1 && out.rows == 4);
> > }
>
>
> As I said, I do not see the pattern; so I cannot propose a solution.
>
> That said: from the original problem description (and to some extent from
> the test cases), it appears that
>
> columns / rows
>
> should be a good approximation to
>
> masterAspectRatio / tileAspectRatio
>
>
> Now, the problem of finding rational best approximations to real numbers is
> solved via continued fractions (google for "rational best approximation" and
> "continued fractions"). Maybe, you can use that as at least as a building
> block for the 2D tiling problem with uniform tiles.

Thanks, I'll have a look.
First  |  Prev  | 
Pages: 1 2
Prev: Faster image rotation
Next: Question: Is there a programming language that meets this criteria?