计算旋转矩形中的最大矩形
我试图find最好的方法来计算可以包含在一个旋转的矩形内的最大（面积）的矩形。
一些图片应该帮助（我希望）在可视化我的意思是：
input矩形的宽度和高度是给定的，旋转angular度也是如此。 输出矩形不旋转或倾斜。
我正在走下一条漫长的路线，我甚至不知道它是否会处理angular落案件（不是双关语）。 我敢肯定，这是一个优雅的解决scheme。 有小费吗？
编辑 ：输出矩形点不一定要触摸input矩形的边缘。 （感谢E先生）
我刚来这里寻找同样的答案。 想到这么多涉及math的事情之后，我以为我会采取半受教育的猜测。 涂了一点，我得出了（直观的，可能不是完全确切的）结论，即最大的矩形与外部矩形的比例成正比，它的两个相对的angular落位于外部矩形的对angular线与旋转的矩形。 对于正方形，对angular线和边的任何一个都可以做…我想我对此很满意，现在开始把我的锈迹斑斑的技能（我知道，可怜的）打磨掉了。
次要更新…pipe理做一些trig计算。 这是当图像的高度大于宽度时的情况。
更新。 得到了整个事情的工作。 这是一些js代码。 它连接到一个更大的程序，大多数variables超出了函数的范围，并且直接从函数内部修改。 我知道这不太好，但我正在使用这个在孤立的情况下，将不会与其他脚本混淆： redacted
我冒昧地清理代码并将其提取到一个函数中：
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 }; } 我遇到了一些gamma计算的问题，并修改了它，以考虑原始盒子在哪个方向上是最长的。
– 马格努斯霍夫
试图不打破传统把解决问题的办法作为一个图片:)
编辑：第三个方程是错误的。 正确的是：
3.w * cos（α）* X + w * sin（α）* Y -w * w * sin（α）* cos（α）-w * h = 0
为了求解线性方程组，可以使用Cramer规则或者Gauss方法 。
首先，我们考虑angular度为零或π/ 2的倍数的平凡情况。 然后最大的矩形与原始矩形相同。
一般来说，内部矩形在外部矩形的边界上将有3个点。 如果没有，那么可以移动它，使得一个顶点位于底部，一个顶点位于左侧。 然后可以放大内部矩形，直到其余两个顶点中的一个碰到边界。
我们称外部矩形R1和R2的边。 不失一般性，我们可以假设R1 <= R2。 如果我们称内部矩形H和W的边，那么我们就有这个
H cos a + W sin a <= R1 H sin a + W cos a <= R2
由于我们至less有3点的边界，至less有一个不平等必须是平等的。 让我们用第一个。 很容易看出：
W = (R1 - H cos a) / sin a
所以面积是
A = HW = H (R1 - H cos a) / sin a
我们可以采取衍生工具。 H并要求它等于0：
dA/dH = ((R1 - H cos a) - H cos a) / sin a
求解H并使用上面的Wexpression式，我们发现：
H = R1 / (2 cos a) W = R1 / (2 sin a)
在第二次不平等中取代这一点，经过一些操纵后，
R1 (tan a + 1/tan a) / 2 <= R2
在左边的因素总是至less为1.如果不等式满足，那么我们有解决scheme。 如果不满意，则解决scheme就是同时满足不平等的一个。 换句话说，它是接触外部矩形的所有四条边的矩形。 这是一个具有2个未知数的线性系统，很容易解决：
H = (R2 cos a - R1 sin a) / cos 2a W = (R1 cos a - R2 sin a) / cos 2a
根据原始坐标，我们得到：
x1 = x4 = W sin a cos a y1 = y2 = R2 sin a - W sin^2 a x2 = x3 = x1 + H y3 = y4 = y2 + W
编辑 ：我的Mathematica答案下面是错误的 – 我正在解决一个稍微不同的问题，而不是我认为你真的问。
为了解决你真正问的问题，我会使用下面的algorithm：
关于最大空矩形问题
使用这种algorithm，表示形成旋转矩形的边界的有限数量的点（可能是100左右，并且确保包括angular落） – 这些将是本文描述的集合S。
。
。
。
。
。
为了后人的缘故，我留下了原文：
具有最大面积的内侧矩形将始终是矩形的下半angular（图中的α附近的angular）等于外侧矩形宽度的一半的矩形。
我有点欺骗和使用Mathematica来解决我的代数：
由此可以看出，内部矩形的最大面积等于angular度的割线乘以angular度的割线的1/4宽度^ 2 *余量。
现在我需要弄清楚这个最佳条件下底angular的x值是多less。 在我的面积公式中使用mathematica中的求解函数，我得到以下结果：
这表明底angular的x坐标等于宽度的一半。
现在只要确定，我会经验地testing我们的答案。 在下面的结果中，您可以看到，实际上我所有testing的最高区域（肯定不是详尽的，但您明白了）是底angular的x值=外矩形宽度的一半。 
@Andri在我testing的width > height图像上工作不正常。 所以，我通过这种方式修改和优化了他的代码（只有两个三angular函数）：
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
此外，我决定发布以下用于比例矩形计算的函数：
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 } }
对不起，这里没有给出一个推导，但是我前几天在Mathematica中解决了这个问题，并提出了以下的程序，非Mathematica的人应该可以读取。 如有疑问，请查阅http://reference.wolfram.com/mathematica/guide/Mathematica.html
下面的过程返回一个矩形的宽度和高度，该矩形的最大面积与另一个宽度为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]}] ] ]
这是做这个最简单的方法… 🙂
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);
Coproc以简单高效的方式在另一个线程（ https://stackoverflow.com/a/16778797 ）上解决了这个问题。 另外，他在那里给出了很好的解释和python代码。
下面是我的Matlab解决scheme的实现：
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://stackoverflow.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([wh]); 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),:);
