Prev: Faster image rotation
Next: Question: Is there a programming language that meets this criteria?
From: Daniel T. on 7 Apr 2010 15:22
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.

Please help. In C I expect the function signature to look something like:

struct Pair {
int rows;
int columns;
};

struct Pair findBestFit(double masterAspectRatio, double
rectAspectRatio, int count);
From: Kai-Uwe Bux on 7 Apr 2010 15:35
Daniel T. wrote:

> 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.
>
> Please help. In C I expect the function signature to look something like:
>
> struct Pair {
> int rows;
> int columns;
> };
>
> struct Pair findBestFit(double masterAspectRatio, double
> rectAspectRatio, int count);

I do not exactly understand the question, but it seems you are looking for a
pair of integers m and n such that m/n is closest to some given real number.

a) Is that number masterAspectRatio or rectAspectRatio? More generally, why
do you have _two_ real numbers as input?

b) What are the constraints on m and n? (Is that something to be derived
from count?)


Best

Kai-Uwe Bux
From: Daniel T. on 7 Apr 2010 15:45
In article <hpimqs$e6d$1(a)news.doubleSlash.org>,
Kai-Uwe Bux <jkherciueh(a)gmx.net> wrote:

> Daniel T. wrote:
>
> > 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.
> >
> > Please help. In C I expect the function signature to look something like:
> >
> > struct Pair {
> > int rows;
> > int columns;
> > };
> >
> > struct Pair findBestFit(double masterAspectRatio, double
> > rectAspectRatio, int count);
>
> I do not exactly understand the question, but it seems you are looking for a
> pair of integers m and n such that m/n is closest to some given real number.
>
> a) Is that number masterAspectRatio or rectAspectRatio? More generally, why
> do you have _two_ real numbers as input?
>
> b) What are the constraints on m and n? (Is that something to be derived
> from count?)

Thanks for the quick response, but as soon as I formulated the question
and the signature and posted it, I found a solution (wouldn't you just
know it!)

struct Pair {
int rows;
int columns;
};

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;
}

I could go with a binary search here, but count is never going to be
over 100 or so, so I'm not sure the gain is worth it.

Now that I'm providing a fully specified solution, maybe you can suggest
a better one?
From: Kai-Uwe Bux on 7 Apr 2010 16:15
Daniel T. wrote:

> In article <hpimqs$e6d$1(a)news.doubleSlash.org>,
> Kai-Uwe Bux <jkherciueh(a)gmx.net> wrote:
>
>> Daniel T. wrote:
>>
>> > 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.
>> >
>> > Please help. In C I expect the function signature to look something
>> > like:
>> >
>> > struct Pair {
>> > int rows;
>> > int columns;
>> > };
>> >
>> > struct Pair findBestFit(double masterAspectRatio, double
>> > rectAspectRatio, int count);
>>
>> I do not exactly understand the question, but it seems you are looking
>> for a pair of integers m and n such that m/n is closest to some given
>> real number.
>>
>> a) Is that number masterAspectRatio or rectAspectRatio? More generally,
>> why do you have _two_ real numbers as input?
>>
>> b) What are the constraints on m and n? (Is that something to be derived
>> from count?)
>
> Thanks for the quick response, but as soon as I formulated the question
> and the signature and posted it, I found a solution (wouldn't you just
> know it!)
>
> struct Pair {
> int rows;
> int columns;
> };
>
> 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.


Best

Kai-Uwe Bux
From: Jongware on 8 Apr 2010 11:09
On 07-Apr-10 21:22 PM, Daniel T. wrote:
> 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.
>
> Please help. In C I expect the function signature to look something like:
>
> struct Pair {
> int rows;
> int columns;
> };
>
> struct Pair findBestFit(double masterAspectRatio, double
> rectAspectRatio, int count);

"Greatest common divisor"?
(http://en.wikipedia.org/wiki/Euclidean_algorithm)

That sounds like the algorithm you are describing.

[Jw]
 |  Next  |  Last
Pages: 1 2
Prev: Faster image rotation
Next: Question: Is there a programming language that meets this criteria?