Rounding an integer such that multiplying it by a float returns a whole number

Question

I'm working on an image scaling application, and I'm given a scaling ratio and a rectangle. I need to multiply the rectangle with the ratio but also make sure that the resulting rectangle is composed of only whole numbers (i.e no floating points). If not, I want to expand the source Rectangle so that the above condition is true.

At the moment I'm brute forcing it (code below). But I'm pretty sure there's a way of doing this using clever math.

RECT AdjustRectWholeNumber(RECT SrcRect, float ratio)
{
    RECT adjustedRect = SrcRect;
    while (!isWholeNumber(adjustedRect.left * ratio))
    {
        adjustedRect.left--;
    }
    while (!isWholeNumber(adjustedRect.top * ratio))
    {
        adjustedRect.top--;
    }
    while (!isWholeNumber(adjustedRect.right * ratio))
    {
        adjustedRect.right++;
    }
    while (!isWholeNumber(adjustedRect.bottom * ratio))
    {
        adjustedRect.bottom++;
    }
    return adjustedRect;
}

Example: Given rect (78,188,1068,790) and ratio 1.25, it should return (76, 188, 1068, 792)

Reasoning: If I was to multiply (78,188,1068,790) by 1.25, it would give me (97.5, 188, 1068, 987.5). This is not ideal because if I round (up or down) the scaled rectangle I lose precision which shows up as small corruption artifacts on the screen. Where as if we expand the source rectangle such that after multiplying by the scaling factor we get all whole numbers, no precision is lost, and thereby no corruption is seen.

NOTE: The scaling ratio is guaranteed to be able to produce whole numbers

Any help is appreciated!

EDIT: Adding code for isWholeNumber as requested

bool isWholeNumber(float f)
{
    if (floor(f) == f)
        return true;
    return false;
}

To clarify let's assume that the only ratios I will ever get are (1.25, 1.5, 1.75, 2.0, 2.25)

You might be better of passing in an actual ratio or fraction (i.e. numerator/denominator as `int`s). Not sure what your function would need to return if I passed in pi? — franji1, Jun 01 '17 at 16:17
"(78,188,1068,790) and ratio 1.25, it should return (76, 188, 1068, 792)"? Shouldn't it be (x',y',1335,988). Pseudocode/Math being `newWidth=((int)(oldWidth * ratio + 0.5f))` 0.5 to account for rounding. The (x',y') would be based on the point you're scaling from. — SGM1, Jun 01 '17 at 16:33
[this question](https://stackoverflow.com/questions/4355640/how-to-convert-float-to-fraction) should do for a good starting-point. — , Jun 01 '17 at 16:57
@SGM1 It's not explained well, but it seems the argument there is `78*1.25` doesn't produce a whole number, but `76*1.25` does, so you convert that before multiplying by the ratio. — Bernhard Barker, Jun 01 '17 at 17:22
@Dukeling Consider the scenario where the ratio is `1/77`. You would hit go does 77, 76,75... all the way to 1. Then multiplying the ratio would not have the proper value. `newWidth=((int)(oldWidth * ratio + 0.5f))` is definitely more correct, it rounds to the nearest integer. — SGM1, Jun 01 '17 at 17:28
@SGM1 I may have phrased it in a less than ideal way, but I meant what Dukeling explained. I've updated the question to reflect that — Sid, Jun 01 '17 at 17:50
@RichardCritten I've updated the question with the code for `isWholeNumber` — Sid, Jun 01 '17 at 17:51
@Paul that question is not relevant. Please re-read the question — Sid, Jun 01 '17 at 18:03
Your reasoning seems flawed - unless you multiply the size by an integer (1,2,3,4,...), pixel-based resizing will need to necessarily duplicate some pixels more than others, leading to what I'm guessing you refer to as "corruption artifacts". Whether the resulting size was rounded up or down by 1 pixel is largely irrelevant to this problem. — Bernhard Barker, Jun 01 '17 at 18:08
@Sid well, say a float is representing a fraction, like `1.25 = 5/4`. Then obviously a number multiplied by `1.25` can only be a whole number, if the number is a multiple of 4. So yes, it is relevant, as it delivers the relevant info to do the first step to a solution without brute-force. — , Jun 01 '17 at 18:23
While this could technically be considered brute force, with a correct isWholeNumber function, on the assumption that ratios can only be those shown, i.e. multiples of 1/4, each while loop will have at most 3 iterations, which is probably good enough for any practical purposes. `floor(f) == f` is unreliable, see [How to check if float is a whole number?](https://stackoverflow.com/questions/15313808/how-to-check-if-float-is-a-whole-number) — Bernhard Barker, Jun 01 '17 at 18:24
Thanks for your input guys! @Dukeling you're right that some pixels will have to be duplicated more than others. The 'corruption artifacts' that I refer to arise because these rectangles are dirty regions of a bigger image in general. I am only re-rendering and scaling these dirty regions on the screen and hence the corruption. — Sid, Jun 01 '17 at 19:08

SergGr · Answer 1 · 2017-06-01T22:40:51.057

I don't think that generally you issue as stated has a good solution. Not all "good" fractions has exact representation as a floating point number (for example 4/3 doesn't). Generally exact representation is possible only for those fractions that has a power of 2 as a denominator. And if you try to use float approximation for "bad" fractions as is, you'll get a fraction with a denominator of about 2^-20 i.e. around 10^-6 fitting which makes no sense. Thus the obvious suggestion is to use some explicit custom type to represent fractions as an explicit (integer) nominator and denominator. And if you have an explicit value for denominator the task becomes trivial. Alternatively if you are sure that

the only ratios I will ever get are (1.25, 1.5, 1.75, 2.0, 2.25)

you can have a simple function that would match values and say if the denominator is 1, 2 or 4. If you have more possible values but all fractions have power of 2 denominators, you also might consider using frexp/frexpf to get exponent (power of 2 of the denominator)

So now when you have an integer denominator, everything is very easy: you just need to find a number that is divisible by it. You can do it with integer division and multiplication (assuming your value is positive):

int roundDown(int value, int denominator) {
    return (value / denominator) * denominator;
}

int roundUp(int value, int denominator) {
    return ((value + denominator - 1) / denominator) * denominator;
}

It should be obvious that those ratios are equivalent to `5/4`, `3/2`, `7/4`, `2/1`, `9/4`. If you can actually express them that way instead of as a floating point ratio, you're golden. It's possible to write a function that returns the nearest numerator/denominator combination for any given number if you accept a limited number of denominators and the resulting possible errors. — Mark Ransom, Jun 02 '17 at 03:32
@MarkRansom, I'm not sure how this comment is different from what I suggest in my answer as "_Thus the obvious suggestion is to use some explicit custom type to represent fractions as an explicit (integer) nominator and denominator._"? — SergGr, Jun 02 '17 at 08:13
It's not different, I was just emphasizing the point you already made. I did that *after* I gave you a +1. — Mark Ransom, Jun 02 '17 at 14:08

Rounding an integer such that multiplying it by a float returns a whole number

1 Answers1