Fit a rectangle into another rectangle

Question

I'm frequently fitting one rectangle into another so that it fits nicely and is centered. I would draw something on the whiteboard and take a picture of what the logic is but it's getting dark and candle light makes it not as fun to do.

Anyway, it's quite straightforward and easy to understand. Here is the function I just had to write out from scratch again (this time in PHP):

// Fit rectangle 2 into rectangle 1 to get rectangle 3
// Rectangle 3 must be centered
// Return dimensions of rectangle and position relative to rectangle 1

function fitrect($w1,$h1,$w2,$h2){

    // Let's take a chance with rectangle 3 width being equal to rectangle 1 width
    $w3=$w1;
    $h3=$w3*($h2/$w2);

    // Check if height breaks rectangle 1 height
    if($h3>$h1){
        // Recalculate dimensions and then position
        $h3=$h1;
        $w3=$h3*($w2/$h2);
        $x3=($w1-$w3)/2;
        $y3=0;
    }else{
        // Just calculate position
        $y3=($h1-$h3)/2;
        $x3=0;
    }

    // Tidy up
    $x3=round($x3);
    $y3=round($y3);
    $w3=round($w3);
    $h3=round($h3);

    // Result array
    $res=array($x3,$y3,$w3,$h3);

    return($res);

}

I'd like to understand this algorithm and other versions of it so that my brain groks the foundations so that I never have to rely on pen and paper (or the whiteboard) again.

So, how would you do this? What fluff can be removed?

EDIT: As an example - say we have rectangle 1 to have dimensions 256x256 and rectangle 2 to be 44x167. Then we need to scale rectangle 2 to 67x256 and position it at 94,0 relative to rectangle 1 so that it sits maximized and centralized in rectangle 1.

Wiesbaden

You have no lights, but a computer to program on? – Criminate

Upvoted for witty post but I don't understand what the third rectangle is. – Yepez

"Anyway, it's quite straightforward and easy to understand."..."I'd like to understand this algorithm and other versions of it..." - What exactly is the question again? – Parson

Let's say the big rectangle is a letter size paper and the small rectangle is an envelope. So...you want to center the envelope on the paper. Now what's the third rectangle? – Yepez

@Criminate Aye, you should see the coat I'm wearing - I can just about move my hands to type. – Wiesbaden

@MiserableVariable Imagine fitting one image into another image. It needs to be scaled for best fit and positioned centrally. – Wiesbaden

If the second image is bigger then first then scale it down, maintaining aspect ratio such that either its width or the height will be same as the first image and the other will be centered? If it is smaller then center both dimensions. Is that the spec? Can you rotate? – Yepez

@MiserableVariable Thats the idea. If its smaller then it needs scaling up. No rotation. See my edit to question for example. – Wiesbaden

Answer 1

Here's how I would do it.

let's define a term, fatness, that is equal to the ratio of a rectangle's width to its height. a rectangle with height 1 and width 10 has fatness 10. A rectangle with height 20 and width 10 has fatness 0.5. When you resize a rectangle, its fatness doesn't change.

When you scale rectangle 2 up or down in size so that its width is equal to rectangle 1, it will not overflow the top or bottom as long as rectangle 2 is fatter than rectangle 1. It will overflow if 1 is fatter than 2. Now you know ahead of time whether to resize for a snug width, or a snug height. Furthermore, the translation logic is the same for both cases, so that can go outside of the if/else block.

in pseudocode: (sorry, I don't know PHP)

fatness1 = w1 / h1
fatness2 = w2 / h2

#adjust scaling
if fatness2 >= fatness1:
    #scale for a snug width
    scaleRatio = w1 / w2
else:
    #scale for a snug height
    scaleRatio = h1 / h2
w3 = w2 * scaleRatio
h3 = h2 * scaleRatio


#adjust rectangle 3's center so it is the same as 1's center
xCenterOf1 = x1 + (w1 / 2)
yCenterOf1 = y1 + (h1 / 2)

x3 = xCenterOf1 - (w3 / 2)
y3 = yCenterOf1 - (h3 / 2)

return (x3, y3, w3, h3)

Testing in python, assuming rectangle 1 is at (0,0), scale(256,256, 44, 167) returns (0.0, 94.3, 256.0, 67.4).

Devastate

I like the idea of 'fatness'. – Wiesbaden

Answer 2

Here's a handy function written in Java.

public static RectF fitRectWithin(Rect inner, Rect outer) {
    float innerAspectRatio = inner.width() / (float) inner.height();
    float outerAspectRatio = outer.width() / (float) outer.height();

    float resizeFactor = (innerAspectRatio >= outerAspectRatio) ?
    (outer.width() / (float) inner.width()) :
    (outer.height() / (float) inner.height());

    float newWidth = inner.width() * resizeFactor;
    float newHeight = inner.height() * resizeFactor;
    float newLeft = outer.left + (outer.width() - newWidth) / 2f;
    float newTop = outer.top + (outer.height() - newHeight) / 2f;

    return new RectF(newLeft, newTop, newWidth + newLeft, newHeight + newTop);
}

Claypool

Answer 3

Here's how I did it. (This algorithm works great with images.) Let's say you have a rectangle, and a container (also a rectangle):

aspectRatio = screen.width / screen.height

if (rectangle.width >= rectangle.height)
{
   resizeFactor = container.width / rectangle.width
   rectangle.width = rectangle.width * resizeFactor
   rectangle.height = rectangle.height * resizeFactor * aspectRatio
}
else
{
   resizeFactor = container.height / rectangle.height
   rectangle.width = rectangle.width * resizeFactor / aspectRatio
   rectangle.height = rectangle.height * resizeFactor
}

You can optimise this algorithm a little bit by changing line 6 to:

rectangle.width = container.width

and the same to line 13 if you want to.

Orose

Answer 4

I just had to deal with something similar: let's call rectangle2 the image, and rectangle1 the window. So our task is to fit an image into the window.

Also in my scenario, both the image and the window have an "inner" coordinates system of [-1,1]X[-1,1]. In fact, inside the window, there is a viewport (rectangle3 in the question) where the image will be projected, and so our task is to find the largest viewport (a rectangle inside window) that has the same aspect ratio (width/height) as image.

The viewport is determined by a fraction of the width/height of the image:

viewport_width = scale_w * window_w
viewport_height = scale_h * window_h

So our goal is to find the right scaling of the width and height of window, such that the viewport will have the same aspect ratio (width/height) as the image:

# goal: 
scale_w * window_w == image_w
scale_h * window_h == image_h

Which means that the scale we are looking for satisfies:

(scale_w / scale_h) == ((image_w / image_h) / (window_w / window_h))

Let's denote the right hand side of this equation by s for a moment.

Since we are looking for the maximal viewport, surely at least one out of scale_w and scale_h will be equal to 1. So - if s<1, meaning the window is wider than the image, we will have scale_w=s, scale_h=1 (this corresponds to the figure above, with scale_w=0.5). And if s>1, meaning the image is wider than the window, we will have scale_w=1, scale_h=1/s.

In python code it looks like this:

def compute_viewport_scale(image_size, window_size):
    image_w, image_h = image_size
    window_w, window_h = window_size
    im_ratio, win_ratio = image_w / image_h, window_w / window_h

    scale = im_ratio / win_ratio
    if scale > 1:  # image is wider than screen
        scale_w = 1
        scale_h = 1 / scale
    else:  # window is wider then image
        scale_w = scale
        scale_h = 1

    viewport_w, viewport_h = window_w * scale_w, window_h * scale_h
    assert (round(viewport_w / viewport_h, 5) == round(image_w / image_h, 5))

    return scale_w, scale_h

Since I wanted to be absolutely sure I have all the cases covered, I constructed a list of examples for sizes, to make sure indeed this formula is correct. And indeed, if you run all these lines, you will get no assert errors :)

# aspect ratio = 1
compute_viewport_scale((100, 100), (100, 100))
compute_viewport_scale((100, 100), (200, 200))
compute_viewport_scale((200, 200), (100, 100))

# image is wider than screen: (im_w / im_h) > (win_w / win_h)  [ i.e. im_ratio > win_ratio ]
# (im_ratio < 1 and win_ratio > 1 cant happen)
# im_w > win_w and im_h > win_h
compute_viewport_scale((300, 200), (100, 90))  # im_ratio > 1 and win_ratio > 1
compute_viewport_scale((200, 300), (100, 200))  # im_ratio < 1 and win_ratio < 1
compute_viewport_scale((300, 200), (100, 150))  # im_ratio > 1 and win_ratio < 1
# im_w > win_w and im_h < win_h
compute_viewport_scale((150, 50), (110, 100))  # im_ratio > 1 and win_ratio > 1
compute_viewport_scale((200, 300), (100, 400))  # im_ratio < 1 and win_ratio < 1
compute_viewport_scale((300, 100), (100, 150))  # im_ratio > 1 and win_ratio < 1
# (im_w < win_w and im_h > win_h cant happen)
# im_w < win_w and im_h < win_h
compute_viewport_scale((150, 50), (200, 100))  # im_ratio > 1 and win_ratio > 1
compute_viewport_scale((90, 100), (100, 200))  # im_ratio < 1 and win_ratio < 1
compute_viewport_scale((110, 100), (100, 200))  # im_ratio > 1 and win_ratio < 1

# image is wider than screen: (im_w / im_h) < (win_w / win_h)  [ i.e. im_ratio < win_ratio ]
# (im_ratio > 1 and win_ratio < 1 cant happen)
# im_w > win_w and im_h > win_h
compute_viewport_scale((300, 200), (100, 50))  # im_ratio > 1 and win_ratio > 1
compute_viewport_scale((200, 400), (100, 150))  # im_ratio < 1 and win_ratio < 1
compute_viewport_scale((200, 400), (150, 100))  # im_ratio < 1 and win_ratio > 1
# (im_w > win_w and im_h < win_h cant happen)
# im_w < win_w and im_h > win_h
compute_viewport_scale((150, 100), (200, 50))  # im_ratio > 1 and win_ratio > 1
compute_viewport_scale((200, 400), (380, 390))  # im_ratio < 1 and win_ratio < 1
compute_viewport_scale((200, 400), (390, 380))  # im_ratio < 1 and win_ratio > 1
# im_w < win_w and im_h < win_h
compute_viewport_scale((300, 200), (600, 300))  # im_ratio > 1 and win_ratio > 1
compute_viewport_scale((200, 300), (500, 600))  # im_ratio < 1 and win_ratio < 1
compute_viewport_scale((50, 100), (300, 200))  # im_ratio < 1 and win_ratio > 1

Lindley