计算旋转矩形中最大的矩形

I'm trying to find the best way to calculate the biggest (in area) rectangle which can be contained inside a rotated rectangle.

我试图找到计算最大(面积)矩形的最佳方法，它可以包含在一个旋转的矩形中。

Some pictures should help (I hope) in visualizing what I mean:

一些图片可以帮助(我希望)在视觉化我的意思:

The width and height of the input rectangle is given and so is the angle to rotate it. The output rectangle is not rotated or skewed.

给出输入矩形的宽度和高度，以及旋转矩形的角度。输出矩形没有旋转或倾斜。

I'm going down the longwinded route which I'm not even sure if it will handle the corner cases (no pun intended). I'm certain there is an elegant solution to this. Any tips?

我正沿着冗长的路线走，我甚至不确定它是否能处理角落里的箱子(没有双关语)。我肯定有一个很好的解决方案。任何建议吗?

EDIT: The output rectangle points don't necessarily have to touch the input rectangles edges. (Thanks to Mr E)

编辑:输出矩形点不一定要触摸输入矩形的边。(由于E)先生

8 个解决方案

#1

I just came here looking for the same answer. After shuddering at the thought of so much math involved, I thought I would resort to a semi-educated guess. Doodling a bit I came to the (intuitive and probably not entirely exact) conclusion that the largest rectangle is proportional to the outer resulting rectangle, and its two opposing corners lie at the intersection of the diagonals of the outer rectangle with the longest side of the rotated rectangle. For squares, any of the diagonals and sides would do... I guess I am happy enough with this and will now start brushing the cobwebs off my rusty trig skills (pathetic, I know).

我只是来找同样的答案。一想到涉及这么多数学知识，我就不寒而栗，于是我想我可以用半熟的猜测。画了一点，我得到了(直觉上的，可能不是完全准确的)结论，最大的矩形与得到的外部矩形成比例，它的两个相对的角位于外部矩形的对角线与旋转矩形的最长边的交点处。对于正方形，任何对角线和边都可以……我想我对此已经很满意了，现在我要开始梳理我那陈旧的三角技巧了(我知道，真可怜)。

Minor update... Managed to do some trig calculations. This is for the case when the Height of the image is larger than the Width.

小更新……做了一些三角运算。这适用于图像的高度大于宽度的情况。

Update. Got the whole thing working. Here is some js code. It is connected to a larger program, and most variables are outside the scope of the functions, and are modified directly from within the functions. I know this is not good, but I am using this in an isolated situation, where there will be no confusion with other scripts: redacted

更新。让整件事顺利进行。这里是一些js代码。它连接到一个更大的程序，并且大多数变量不在函数的范围内，并且直接从函数内部进行修改。我知道这不是很好，但是我在一个孤立的情况下使用它，在这种情况下不会与其他脚本混淆:编校

---

I took the liberty of cleaning the code and extracting it to a function:

我*地清理代码并将其提取为一个函数:

function getCropCoordinates(angleInRadians, imageDimensions) {
    var ang = angleInRadians;
    var img = imageDimensions;

    var quadrant = Math.floor(ang / (Math.PI / 2)) & 3;
    var sign_alpha = (quadrant & 1) === 0 ? ang : Math.PI - ang;
    var alpha = (sign_alpha % Math.PI + Math.PI) % Math.PI;

    var bb = {
        w: img.w * Math.cos(alpha) + img.h * Math.sin(alpha),
        h: img.w * Math.sin(alpha) + img.h * Math.cos(alpha)
    };

    var gamma = img.w < img.h ? Math.atan2(bb.w, bb.h) : Math.atan2(bb.h, bb.w);

    var delta = Math.PI - alpha - gamma;

    var length = img.w < img.h ? img.h : img.w;
    var d = length * Math.cos(alpha);
    var a = d * Math.sin(alpha) / Math.sin(delta);

    var y = a * Math.cos(gamma);
    var x = y * Math.tan(gamma);

    return {
        x: x,
        y: y,
        w: bb.w - 2 * x,
        h: bb.h - 2 * y
    };
}

I encountered some problems with the gamma-calculation, and modified it to take into account in which direction the original box is the longest.

我遇到了一些计算伽玛的问题，我修改了它，考虑到原来盒子的最长方向。

-- Magnus Hoff

——马格纳斯霍夫

#2

Trying not to break tradition putting the solution of the problem as a picture:)

试着不打破传统，把问题的解决方案画成一幅图:

---

Edit: Third equations is wrong. The correct one is:

编辑:第三个方程是错误的。正确的是:

3.w * cos(α) * X + w * sin(α) * Y - w * w * sin(α) * cos(α) - w * h = 0

3所示。w * cos(α)* X + w * sin(α)* Y - w * w * sin(α)* cos(α)- w * h = 0

To solve the system of linear equations you can use Cramer rule, or Gauss method.

要解线性方程组，可以用克莱默规则或高斯方法。

#3

First, we take care of the trivial case where the angle is zero or a multiple of pi/2. Then the largest rectangle is the same as the original rectangle.

首先，我们考虑一个平凡的情况，角度是0或/2的倍数。那么最大的矩形与原始矩形相同。

In general, the inner rectangle will have 3 points on the boundaries of the outer rectangle. If it does not, then it can be moved so that one vertex will be on the bottom, and one vertex will be on the left. You can then enlarge the inner rectangle until one of the two remaining vertices hits a boundary.

一般来说，内矩形在外矩形的边界上有3个点。如果没有，那么它可以被移动，这样一个顶点在底部，一个顶点在左边。然后你可以放大内矩形，直到剩下的两个顶点中的一个到达边界。

We call the sides of the outer rectangle R1 and R2. Without loss of generality, we can assume that R1 <= R2. If we call the sides of the inner rectangle H and W, then we have that

我们把外面的矩形叫做R1和R2。在不损失通用性的前提下，我们可以假设R1 <= R2。如果我们把内矩形的边称为H和W，那么我们就得到了这个。

H cos a + W sin a <= R1
H sin a + W cos a <= R2

Since we have at least 3 points on the boundaries, at least one of these inequality must actually be an equality. Let's use the first one. It is easy to see that:

既然我们在边界上至少有3个点，那么至少有一个不等式是相等的。我们用第一个。很容易看出:

W = (R1 - H cos a) / sin a

and so the area is

所以面积是

A = H W = H (R1 - H cos a) / sin a

We can take the derivative wrt. H and require it to equal 0:

我们可以对它求导。H要求它等于0:

dA/dH = ((R1 - H cos a) - H cos a) / sin a

Solving for H and using the expression for W above, we find that:

解H，用上面W的表达式，我们发现:

H = R1 / (2 cos a)
W = R1 / (2 sin a)

Substituting this in the second inequality becomes, after some manipulation,

把这个代入第二个不等式，经过一些操作，

R1 (tan a + 1/tan a) / 2 <= R2

The factor on the left-hand side is always at least 1. If the inequality is satisfied, then we have the solution. If it isn't satisfied, then the solution is the one that satisfies both inequalities as equalities. In other words: it is the rectangle which touches all four sides of the outer rectangle. This is a linear system with 2 unknowns which is readily solved:

左边的因子总是至少为1。如果不等式被满足，我们就得到了解。如果它不满足，那么解就是满足两个不等式的等式。换句话说:它是一个矩形，它与外部矩形的所有四个边相连。这是一个线性系统，有两个未知数，很容易解出来:

H = (R2 cos a - R1 sin a) / cos 2a
W = (R1 cos a - R2 sin a) / cos 2a

In terms of the original coordinates, we get:

对于原始坐标，我们得到:

x1 = x4 = W sin a cos a
y1 = y2 = R2 sin a - W sin^2 a 
x2 = x3 = x1 + H
y3 = y4 = y2 + W

#4

Edit: My Mathematica answer below is wrong - I was solving a slightly different problem than what I think you are really asking.

编辑:我的Mathematica的答案是错误的——我解决的问题和你想问的有点不同。

To solve the problem you are really asking, I would use the following algorithm(s):

为了解决你真正想问的问题，我将使用以下算法:

On the Maximum Empty Rectangle Problem

最大空矩形问题

Using this algorithm, denote a finite amount of points that form the boundary of the rotated rectangle (perhaps a 100 or so, and make sure to include the corners) - these would be the set S decribed in the paper.

使用这个算法，表示一个有限数量的点，它构成了旋转矩形的边界(可能是100个左右，并确保包括角)-这些是在纸上的集合S。

.

。

.

。

.

。

.

。

.

。

For posterity's sake I have left my original post below:

为了子孙后代的利益，我在下面留下了我最初的帖子:

The inside rectangle with the largest area will always be the rectangle where the lower mid corner of the rectangle (the corner near the alpha on your diagram) is equal to half of the width of the outer rectangle.

最大区域内的矩形将永远是矩形，在矩形中，矩形的中转角(在你的图上靠近alpha的角)等于外部矩形宽度的一半。

I kind of cheated and used Mathematica to solve the algebra for me:

我作弊了，用Mathematica解决了我的代数问题:

From this you can see that the maximum area of the inner rectangle is equal to 1/4 width^2 * cosecant of the angle times the secant of the angle.

从这可以看出,内部的最大区域矩形宽度等于1/4 ^ 2 * csc的角倍sec的角。

Now I need to figure out what is the x value of the bottom corner for this optimal condition. Using the Solve function in mathematica on my area formula, I get the following:

现在我要算出这个最优条件下角的x值是多少。在我的面积公式上使用mathematica中的求解函数，我得到以下结果:

Which shows that the x coordinate of the bottom corner equals half of the width.

这表明，下角的x坐标等于宽度的一半。

Now just to make sure, I'll going to test our answer empirically. With the results below you can see that indeed the highest area of all of my tests (definately not exhaustive but you get the point) is when the bottom corner's x value = half of the outer rectangle's width.

为了确保，我将用经验来检验我们的答案。通过下面的结果，你可以看到我所有的测试的最高区域(当然不是完全的，但是你得到了重点)是当底部角的x值等于外部矩形宽度的一半。

#5

@Andri is not working correctly for image where width > height as I tested. So, I fixed and optimized his code by such way (with only two trigonometric functions):

@Andri在我测试的宽度为>的图像中不能正常工作。所以我对他的代码进行了修正和优化(只有两个三角函数):

calculateLargestRect = function(angle, origWidth, origHeight) {
    var w0, h0;
    if (origWidth <= origHeight) {
        w0 = origWidth;
        h0 = origHeight;
    }
    else {
        w0 = origHeight;
        h0 = origWidth;
    }
    // Angle normalization in range [-PI..PI)
    var ang = angle - Math.floor((angle + Math.PI) / (2*Math.PI)) * 2*Math.PI; 
    ang = Math.abs(ang);      
    if (ang > Math.PI / 2)
        ang = Math.PI - ang;
    var sina = Math.sin(ang);
    var cosa = Math.cos(ang);
    var sinAcosA = sina * cosa;
    var w1 = w0 * cosa + h0 * sina;
    var h1 = w0 * sina + h0 * cosa;
    var c = h0 * sinAcosA / (2 * h0 * sinAcosA + w0);
    var x = w1 * c;
    var y = h1 * c;
    var w, h;
    if (origWidth <= origHeight) {
        w = w1 - 2 * x;
        h = h1 - 2 * y;
    }
    else {
        w = h1 - 2 * y;
        h = w1 - 2 * x;
    }
    return {
        w: w,
        h: h
    }
}

UPDATE

更新

Also I decided to post the following function for proportional rectange calculating:

我还决定发布以下函数进行比例重计算:

calculateLargestProportionalRect = function(angle, origWidth, origHeight) {
    var w0, h0;
    if (origWidth <= origHeight) {
        w0 = origWidth;
        h0 = origHeight;
    }
    else {
        w0 = origHeight;
        h0 = origWidth;
    }
    // Angle normalization in range [-PI..PI)
    var ang = angle - Math.floor((angle + Math.PI) / (2*Math.PI)) * 2*Math.PI; 
    ang = Math.abs(ang);      
    if (ang > Math.PI / 2)
        ang = Math.PI - ang;
    var c = w0 / (h0 * Math.sin(ang) + w0 * Math.cos(ang));
    var w, h;
    if (origWidth <= origHeight) {
        w = w0 * c;
        h = h0 * c;
    }
    else {
        w = h0 * c;
        h = w0 * c;
    }
    return {
        w: w,
        h: h
    }
}

#6

Here is the easiest way to do this... :)

这是最简单的方法。:)

Step 1
//Before Rotation

int originalWidth = 640;
int originalHeight = 480;

Step 2
//After Rotation
int newWidth = 701;  //int newWidth = 654;  //int newWidth = 513;
int newHeight = 564; //int newHeight = 757; //int newHeight = 664;

Step 3
//Difference in height and width
int widthDiff ;
int heightDiff;
int ASPECT_RATIO = originalWidth/originalHeight; //Double check the Aspect Ratio

if (newHeight > newWidth) {

    int ratioDiff = newHeight - newWidth;
    if (newWidth < Constant.camWidth) {
        widthDiff = (int) Math.floor(newWidth / ASPECT_RATIO);
        heightDiff = (int) Math.floor((originalHeight - (newHeight - originalHeight)) / ASPECT_RATIO);
    }
    else {
        widthDiff = (int) Math.floor((originalWidth - (newWidth - originalWidth) - ratioDiff) / ASPECT_RATIO);
        heightDiff = originalHeight - (newHeight - originalHeight);
    }

} else {
    widthDiff = originalWidth - (originalWidth);
    heightDiff = originalHeight - (newHeight - originalHeight);
}

Step 4
//Calculation
int targetRectanleWidth = originalWidth - widthDiff;
int targetRectanleHeight = originalHeight - heightDiff;

Step 5
int centerPointX = newWidth/2;
int centerPointY = newHeight/2;

Step 6
int x1 = centerPointX - (targetRectanleWidth / 2); 
int y1 = centerPointY - (targetRectanleHeight / 2);
int x2 = centerPointX + (targetRectanleWidth / 2);
int y2 = centerPointY + (targetRectanleHeight / 2);

Step 7
x1 = (x1 < 0 ? 0 : x1);
y1 = (y1 < 0 ? 0 : y1);

#7

sorry for not giving a derivation here, but I solved this problem in Mathematica a few days ago and came up with the following procedure, which non-Mathematica folks should be able to read. If in doubt, please consult http://reference.wolfram.com/mathematica/guide/Mathematica.html

抱歉这里没有给出推导，但是几天前我在Mathematica解决了这个问题然后提出了下面的程序，非Mathematica的人应该能读懂。如果有疑问，请咨询http://reference.wolfram.com/mathematica/guide/Mathematica.html

The procedure below returns the width and height for a rectangle with maximum area that fits into another rectangle of width w and height h that has been rotated by alpha.

下面的过程返回一个矩形的宽度和高度，该矩形的最大面积与另一个矩形的宽度w和高度h相匹配，这个矩形已经被阿尔法旋转。

CropRotatedDimensionsForMaxArea[{w_, h_}, alpha_] := 
With[
  {phi = Abs@Mod[alpha, Pi, -Pi/2]},
  Which[
   w == h, {w,h} Csc[phi + Pi/4]/Sqrt[2],
   w > h, 
     If[ Cos[2 phi]^2 < 1 - (h/w)^2, 
       h/2 {Csc[phi], Sec[phi]}, 
       Sec[2 phi] {w Cos[phi] - h Sin[phi], h Cos[phi] - w Sin[phi]}],
   w < h, 
     If[ Cos[2 phi]^2 < 1 - (w/h)^2, 
       w/2 {Sec[phi], Csc[phi]}, 
       Sec[2 phi] {w Cos[phi] - h Sin[phi], h Cos[phi] - w Sin[phi]}]
  ]
]

#8

Coproc solved this problem on another thread (https://*.com/a/16778797) in a simple and efficient way. Also, he gave a very good explanation and python code there.

Coproc在另一个线程(https://*.com/a/16778797)上以简单而有效的方式解决了这个问题。此外，他给出了很好的解释和python代码。

Below there is my Matlab implementation of his solution:

下面是我的Matlab实现他的解决方案:

function [ CI, T ] = rotateAndCrop( I, ang )
%ROTATEANDCROP Rotate an image 'I' by 'ang' degrees, and crop its biggest
% inner rectangle.

[h,w,~] = size(I);
ang = deg2rad(ang);

% Affine rotation
R = [cos(ang) -sin(ang) 0; sin(ang) cos(ang) 0; 0 0 1];
T = affine2d(R);
B = imwarp(I,T);

% Largest rectangle
% solution from https://*.com/a/16778797

wb = w >= h;
sl = w*wb + h*~wb;
ss = h*wb + w*~wb;

cosa = abs(cos(ang));
sina = abs(sin(ang));

if ss <= 2*sina*cosa*sl
    x = .5*min([w h]);
    wh = wb*[x/sina x/cosa] + ~wb*[x/cosa x/sina];
else
    cos2a = (cosa^2) - (sina^2);
    wh = [(w*cosa - h*sina)/cos2a (h*cosa - w*sina)/cos2a]; 
end

hw = flip(wh);

% Top-left corner
tl = round(max(size(B)/2 - hw/2,1));

% Bottom-right corner
br = tl + round(hw);

% Cropped image
CI = B(tl(1):br(1),tl(2):br(2),:);