Jump to content
  • Advertisement
Sign in to follow this  
Andrew Russell

Integer Shrinking Algo [answered]

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
How about this?

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by joanusdmentia
This 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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Quote:
Original post by joanusdmentia
This will automatically distribute the 'leftover' bits for you:

That is exactly what I posted above


So it is, I hadn't even noticed. Sorry, my bad!

Share this post


Link to post
Share on other sites
Quote:
Original post by nhatkthanh
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.


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 this post


Link to post
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 this post


Link to post
Share on other sites
Extrarius: That's what I was describing.

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!