This topic is 4881 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

OK, I'm trying to come up with a good way of shrinking integer-sized regions to fit into a certian ammount of space. Say my regions have the following pixel sizes [100][100][200], and I want to fit them in a space, say 330 pixels in size. The idea being they will each scale down nicely to look something like [83][83][164] (adds up to 330). It must use up all the space available to it, but it dosn't matter if things are a small ammount off. Not converting to floating point and back is highly preferable. Anyone have any ideas? For anyone interested, my current (broken) algo looks something like this:
// The values here are from [100][100][200]

// The Greatest Common Divisor of the different regions
int gcd = FindGCD(); // 100
int normal = TotalSize(); // 400
int available = AvailableSize(); // 330

// "chunk" is what big chunks to alocate to each element
int chunk = available/(normal/gcd); // 82
// "spare" is the size remaining after the alocation of chunks
int spare = available%(normal/gcd); // 2

for( /* each element, e */ )
{
int e.final = chunk*(e.size/gcd);

// hand out "spare" space first-come-first-served
e.final += (e.size/gcd);
spare -= (e.size/gcd);
if(spare < 0) // if we use up more spare than we have, give it back
{
e.final += spare;
spare = 0;
}
}


Anyway, that all works nicely, and gets the results [83][83][164], however once I tried it on some program-generated data it fell appart, because the GCD was way too small (like, 1). Say for instance, the sizes become [100][100][201], then the result is something like:
gcd = 1;
normal = 400;
available = 330;
chunk = available/(normal/gcd) = 0;
spare = available%(normal/gcd) = 330;

And as the spare is alocated to the first element as it needs it, the result is something like [100][100][130], which fills up the space, but is 70 pixels off correct. So yeah - any ideas? [Edited by - Andrew Russell on May 13, 2005 2:58:25 AM]

##### Share on other sites

Start off with:
a[0] = 100; a[1] = 100; a[2] = 200;int Count = 3;int desiredSize = 330;

b holds the resulting sizes:
int sum = 0;for (int i=0; i < Count ;i++) {  sum += a;}for (int j=0; j < Count ;j++) {  b[j] = (a[j] * desiredSize) / sum;  //Or perhaps add rounding to the above by using:  //b[j] = (a[j] * desiredSize + sum/2) / sum;  desiredSize -= b[j]; //subtract from used space  sum -= a[j]; //subtract from original space}

##### Share on other sites
int currenttotal = 0; int temptotal = 0; int desiredtotal = TotalSize();for ( /* each element, e */ ) {  currenttotal += e.size;}for ( /* each element, e */ ) {  // Integer arithmetic. To avoid round-off error we must do the multiplication  // first. The result will be the floor of what the FP value would have been  // if we were doing this the obvious slow way. Thus the total of e.size's will  // be *at most* desiredtotal after this step.  e.size = (e.size * desiredtotal) / currenttotal;  temptotal += e.size;}// Distribute the remainder, desiredtotal-temptotal, among the elements somehow.

##### Share on other sites
This will automatically distribute the 'leftover' bits for you:

int currenttotal= ...;int desiredtotal = ...;int currentsizes[] = ...;int newsizes[] = ...;for(int i=0 ; i<numelements ; ++i){    newsizes = (currentsizes*desiredtotal)/currenttotal;    currenttotal -= currentsizes;    desiredtotal -= newsizes;}

##### Share on other sites
Quote:
 Original post by joanusdmentiaThis will automatically distribute the 'leftover' bits for you:

That is exactly what I posted above, except that you can get a more accurate answer by rounding like this...
int currenttotal = ...;int desiredtotal = ...;int currentsizes[] = ...;int newsizes[] = ...;for (int i=0; i < numelements; ++i){    newsizes = (currentsizes*desiredtotal + currenttotal/2) / currenttotal;    currenttotal -= currentsizes;    desiredtotal -= newsizes;}
It will still come out to exactly desiredtotal, but will be more accurately divided.

##### Share on other sites
add all the values together then get the common scaling factor, so in your case 330/400. Then multiply each value with the scaling factor then you're done e.g 100 * 330/400 ~ 82 or 83 depend on rounding.

##### Share on other sites
Quote:
Original post by iMalc
Quote:
 Original post by joanusdmentiaThis will automatically distribute the 'leftover' bits for you:

That is exactly what I posted above

##### Share on other sites
Quote:
 Original post by nhatkthanhadd all the values together then get the common scaling factor, so in your case 330/400. Then multiply each value with the scaling factor then you're done e.g 100 * 330/400 ~ 82 or 83 depend on rounding.

Won't work because of the integer math. Integer math is rounded down, so you'll have [82][82][165] which adds up to 329, not 330.

##### Share on other sites
Can you explain what you mean by 'shrinking integer-sized regions to fit into a certian ammount of space'? It sounds like you just want linear scaling of a set of numbers so they have a certain sum, in which case you just need to multiply all numbers by DesiredSum/ActualSum

Ex:
{100,100,201}
Total = 401
Desired = 330
Result = {100*330/401, 100*330/401, 200*330/401} = {82, 82, 164}
Result Total = 328
Spare = 2
Evenly distribute it (1 to each cell until you run out, since its rounder error and will never be larger than the number of cells) and you get {83, 83, 164}

Without floating point that is the best you can do (unless you want to work with numbers*10 to get an extra digit of accuracy then scale down for ex, but then you'll still get 'spare' at the end and have to distribute it).

##### Share on other sites
Extrarius: That's what I was describing.

joanus, iMalc: Brilliant (for handling the "redistribution" naturally).

1. 1
2. 2
3. 3
Rutin
18
4. 4
5. 5
frob
11

• 9
• 19
• 9
• 31
• 16
• ### Forum Statistics

• Total Topics
632617
• Total Posts
3007458

×