计算旋转矩形中的最大矩形 [英] Calculate largest rectangle in a rotated rectangle

问题描述

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

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:输出矩形点不一定要接触输入矩形边缘.(感谢E先生)

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

推荐答案

我只是来这里寻找相同的答案.想到涉及这么多数学，我不寒而栗，我想我会诉诸于半知半解的猜测.稍微涂鸦一下，我得出了(直观的，可能并不完全准确)结论，即最大的矩形与生成的外部矩形成正比，它的两个对角位于外部矩形的对角线与矩形的最长边的交点处.旋转的矩形.对于正方形，任何对角线和边都可以...我想我对此很满意，现在将开始清除我生锈的三角技能上的蜘蛛网(可悲，我知道).

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.

更新.搞定了整个事情.这是一些js代码.它连接到一个更大的程序，大多数变量都在函数的范围之外，直接在函数内部修改.我知道这不好，但我在孤立的情况下使用它，不会与其他脚本混淆:redacted

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

我冒昧地清理了代码并将其提取到一个函数中:

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

我在gamma-计算中遇到了一些问题，并修改了它以考虑原始框在哪个方向最长.

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

-- 马格努斯霍夫

这篇关于计算旋转矩形中的最大矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！