Calculate largest rectangle in a rotated rectangle?

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 To solve the system of linear equations you can use Cramer rule or Gauss method.

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 To solve the system of linear equations you can use Cramer rule, or Gauss method.

Good work, have removed my answer. – Mr E Apr 26 at 13:41 Thank you! @Mr E.

– Mihran Hovsepyan Apr 26 at 13:44 How is it possible to put P, Q, R, S to equations 1, 2, 3, and 4? Please give a sample on a substitution into one of the 4 equations. Thank you.

– Legend of Cage Apr 26 at 14:12 P should be puted in first equation (which is equation of line (A, B)). And because P(x1, y1) is on that line, the x1 and y1 should be such that the equality w * cos(a) * x1 + w * sin(a) * y1 -w * w * sin(a) * cos(a) = 0 holds. – Mihran Hovsepyan Apr 26 at 14:20 @Mihran Hovsepyan thanks for that.

I'll look into it and see if I can grok it. – zaf Apr 267 at 7:28.

Edit: My Mathematica answer below is wrong - I was solving a slightly different problem than what I think you are really asking. 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. .. ... 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.

I kind of cheated and used Mathematica to solve the algebra for me: 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. 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: Which shows that the x coordinate of the bottom corner equals half of the width.

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.

– zaf Apr 26 at 13:30 1 Jason, please consider participating in the mathematica tag. – Mr.Wizard Apr 26 at 21:06 @Mr. Recruiting? – belisarius Apr 27 at 3:25 @belisarius sure, why not?

:-) – Mr.Wizard Apr 27 at 6:44.

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: var imgW; //original image width var imgH; //original image Height var angle; //angle of rotation, in degrees var canvasW; //Width of canvas containing rotated image var canvasH; //Height of canvas containing rotated image var cropX, cropY, cropW, cropH; //Crop coordinates, X, Y, Width and Height. //performs the rotation in the UI, and calculates the outer canvas function performRotation(){ if (angle360){ angle = angle-360; } var W; var H; var a; if (angle%180 imgH){ //if image is horizontal if (angle%180 Cos(alpha); var a = d * Math. Sin(alpha)/Math.

Sin(delta); var y = a*Math. Cos(gamma); var x = y*Math. Tan(gamma); var cw = W-2*x; var ch = H-2*y; } else { //or angle in the second or fourth quadrants var W=canvasW; var H=canvasH; var w=imgW; var h=imgH; var alpha = deg2rad(180-angle%180); var beta = deg2rad(rad2deg(alpha) -90) ; var gamma = Math.

Atan(W/H); var delta = deg2rad(180-(rad2deg(alpha)+rad2deg(gamma))); var d = w* Math. Cos(alpha); var a = d * Math. Sin(alpha)/Math.

Sin(delta); var x = a*Math. Cos(gamma); var y = x*Math. Tan(gamma); var cw = W-2*x; var ch = H-2*y; } } cropX=parseInt(Math.

Abs(x)); cropY=parseInt(Math. Abs(y)); cropW=parseInt(cw); cropH=parseInt(ch); }.

Nice graphics. I'll think about this idea. If you manage to produce code then please post it here!

– zaf Sep 22 at 14:30 I am working on the same problem right now. Trying to build a WYSIWYG front-end for some server-based image rotation and cropping. I did some calculations too.

Posting them here. As images.... I haven't coded anything yet. – Andri Sep 22 at 16:54 Done.

The code needs some cleanup, but it's working fine. – Andri Sep 23 at 18:47.

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. 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. We call the sides of the outer rectangle R1 and R2.

Without loss of generality, we can assume that R1 It is easy to see that: 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: 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 = 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 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: 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.

Nice. I'll check it out. – zaf Sep 23 at 10:18 @zaf AFAIK, my answer is the only correct one.

– Jeffrey Sax Sep 26 at 16:33 I'll try to find some time to check your solution. Can you see a quick way to get the xy position (one will do if there are multiple positions) of the target inner rectangle? – zaf Sep 27 at 14:07.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.