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

Question

我正在尝试找到计算最大(面积)矩形的最佳方法,该矩形可以包含在旋转的矩形内.

一些图片应该有助于(我希望)可视化我的意思:

给出输入矩形的宽度和高度,以及旋转它的角度.输出矩形不会旋转或倾斜.

我正沿着漫长的路线往下走,我甚至不确定它是否会处理角落的情况(没有双关语).我确信这有一个优雅的解决方案.有小费吗？

编辑:输出矩形点不一定要触摸输入矩形边.(感谢E先生)

Answer 1

我刚来这里寻找相同的答案.在想到如此多的数学考虑之后,我想我会采用半教育的猜测.有点涂鸦我得出(直观的,可能不完全准确)的结论,即最大的矩形与外部产生的矩形成比例,并且它的两个相对的角位于外部矩形的对角线与最长边的交点处.旋转的矩形.对于正方形,任何对角线和侧面都可以......我想我对此很开心,现在开始刷掉我生锈的触发技术的蜘蛛网(可怜,我知道).

次要更新...管理进行一些三角形计算.这适用于图像高度大于宽度的情况.

更新.得到了整个工作.这是一些js代码.它连接到一个更大的程序,大多数变量超出了函数的范围,并直接从函数内部进行修改.我知道这不好,但我在一个孤立的情况下使用它,在那里不会与其他脚本混淆:编辑

我冒昧地清理代码并将其解压缩到一个函数:

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-calculation中遇到了一些问题,并对其进行了修改,以考虑原始框最长的方向.

- 马格努斯霍夫

Answer 2

试图不打破传统把问题的解决方案作为图片:)

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

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

要求解线性方程组,可以使用Cramer法则或Gauss法.

Answer 3

首先,我们处理角度为零或pi/2的倍数的平凡情况.然后最大的矩形与原始矩形相同.

通常,内部矩形在外部矩形的边界上将具有3个点.如果没有,则可以移动它,使得一个顶点位于底部,一个顶点位于左侧.然后,您可以放大内部矩形,直到其余两个顶点中的一个碰到边界.

我们称外部矩形R1和R2的边.不失一般性,我们可以假设R1 <= R2.如果我们调用内部矩形H和W的边,那么我们就有了

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

由于我们在边界上至少有3个点,因此这些不等式中的至少一个实际上必须是相等的.让我们使用第一个.很容易看出:

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

所以该地区是

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

我们可以采用衍生工具.H并要求它等于0:

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

求解H并使用上面W的表达式,我们发现:

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

在经过一些操纵之后,将其替换为第二个不等式

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

左侧的因子总是至少为1.如果满足不等式,那么我们就有了解决方案.如果不满意,那么解决方案就是满足两个不等式作为等式的解决方案.换句话说:它是接触外部矩形的所有四个边的矩形.这是一个有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

Answer 4

编辑:下面我的Mathematica答案是错误的 - 我解决的问题与我认为你真正要问的问题略有不同.

要解决你真正要问的问题,我会使用以下算法:

关于最大空矩形问题

使用这个算法,表示形成旋转矩形边界的有限数量的点(可能是100左右,并确保包括角) - 这些将是文中描述的集合S.

.

.

.

.

.

为了后人的缘故,我把原来的帖子留在了下面:

具有最大面积的内部矩形将始终是矩形,其中矩形的下中间角(图中的alpha附近的角)等于外部矩形的宽度的一半.

我有点欺骗并使用Mathematica为我解决代数:

由此可以看出,内部矩形的最大面积等于1/4宽度^ 2*角度的cosecant乘以角度的割线.

现在我需要弄清楚这个最佳条件下底角的x值是多少.在mathematica中使用我的区域公式中的Solve函数,我得到以下结果:

这表明底角的x坐标等于宽度的一半.

现在只是为了确保,我将根据经验测试我们的答案.通过下面的结果,您可以看到我的所有测试中的最高区域(肯定不是详尽的,但是您得到的结果)是底角的x值=外部矩形宽度的一半.

Answer 5

@Andri在width > height我测试的图像中无法正常工作.所以,我通过这种方式修复和优化了他的代码(只有两个三角函数):

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
    }
}