Calculate the largest rectangle in a rotating rectangle

Question

I am trying to find the best way to calculate the largest rectangle (in the area) that can be contained inside a rotating rectangle.

Some photos should help (I hope) to visualize what I mean:

Given the width and height of the input rectangle, as well as the angle of rotation. The output rectangle does not rotate or skew.

I follow a long route, and I’m not even sure if he can handle corner affairs (no pun intended). I am sure there is an elegant solution. Any tips?

EDIT : The output rectangles do not have to touch the edges of the input rectangles. (Thanks to Mr. E)

Answer 1

I just came here to find the same answer. After I shuddered at the thought of such a great involvement in mathematics, I thought that I would resort to a semi-educated guess. Doodling, I came to a little (intuitive and probably not quite accurate) conclusion that the largest rectangle is proportional to the outer resulting rectangle, and its two opposite angles 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 will be ... I think I'm quite pleased with this and now I will begin to clean the web of my rusty trigger skills (sorry, I know).

Minor update ... Controlled by some trigger calculations. This applies when the height of the image is greater than the width.

Update Everything is working. Here are some js codes. It is associated with a larger program, and most variables go beyond functions and change directly from functions. I know this is not good, but I use it in an isolated situation where there will be no confusion with other scenarios: redacted

---

I took responsibility for clearing the code and extracting it from the 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 ran into some problems with gamma calculating and modified it to take into account in which direction the source block is the longest.

- Magnus Hoff

Answer 2

Trying not to break the tradition by setting the solution to the problem as pictures :)

---

Edit: Third equations are incorrect. Right:

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

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

Answer 3

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

In general, the inner rectangle will have 3 points on the borders of the outer rectangle. If this is not the case, then it can be moved so that one vertex is at the bottom and one vertex is on the left. You can then enlarge the inner rectangle until one of the two remaining vertices reaches the border.

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

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

Since there are at least 3 points on the boundaries, at least one of these inequalities should actually be equality. Let me use the first one. It is easy to see that:

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

and therefore the area

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

We can take the derivative with respect to. H and require that it be 0:

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

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

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

Substituting this into the second inequality, it becomes after some manipulations

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

The coefficient on the left side is always not less than 1. If the inequality holds, then we have a solution. If this is not satisfied, then the solution is one that satisfies both inequalities as equalities. In other words: it is a rectangle that touches all four sides of the outer rectangle. This is a linear system with two unknowns that can be easily solved:

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

In terms of the initial coordinates, we obtain:

 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

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

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

About the problem of the maximum empty rectangle

Using this algorithm, we denote the finite number of points that form the boundary of the rotating rectangle (maybe about 100 or so, and be sure to include the corners) - this will be the set S described in the document.

.

.

.

.

.

For posterity, I left my original post below:

The inner rectangle with the largest area will always be the rectangle where the bottom middle corner of the rectangle (the angle near the alpha in your diagram) is equal to half the width of the outer rectangle.

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

This shows that the maximum area of ​​the inner rectangle is 1/4 of the width ^ 2 * of the cosecant of the angle times the secant angle.

Now I need to find out what is the x value of the lower angle for this optimal condition. Using the Solve function in math according to my area formula, I get the following:

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

Now, to be sure, I will empirically verify our answer. With the results below, you can see that the really highest area of ​​all my tests (definitely not exhaustive, but you get the point) is when the bottom corner x = half the width of the outer rectangle.

Answer 5

@Andri does not work correctly for an image where width > height , as I tested. So, I fixed and optimized his code in this way (with only two trigonometric functions):

 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

I also decided to publish the following function for proportionally calculating a rectangle:

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

Answer 6

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

The following procedure returns the width and height of a rectangle with a maximum area that fits in another rectangle of width w and height h, which was rotated alpha.

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

Answer 7

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

Answer 8

Coproc solved this problem in a different thread ( https://stackoverflow.com/a/12630/ ... ) in a simple and efficient way. In addition, he gave a very good explanation and python code.

Below is my Matlab implementation of its solution:

 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 /questions/121230/rotate-image-and-crop-out-black-borders/741827#741827 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),:);