The math behind this solution/implementation is equivalent to this solution of an analagous question, but the formulas are simplified and avoid singularities. This is python code with the same interface as largest_rotated_rect
from the other solution, but giving a bigger area in almost all cases (always the proven optimum):
def rotatedRectWithMaxArea(w, h, angle):
"""
Given a rectangle of size wxh that has been rotated by 'angle' (in
radians), computes the width and height of the largest possible
axis-aligned rectangle (maximal area) within the rotated rectangle.
"""
if w <= 0 or h <= 0:
return 0,0
width_is_longer = w >= h
side_long, side_short = (w,h) if width_is_longer else (h,w)
# since the solutions for angle, -angle and 180-angle are all the same,
# if suffices to look at the first quadrant and the absolute values of sin,cos:
sin_a, cos_a = abs(math.sin(angle)), abs(math.cos(angle))
if side_short <= 2.*sin_a*cos_a*side_long or abs(sin_a-cos_a) < 1e-10:
# half constrained case: two crop corners touch the longer side,
# the other two corners are on the mid-line parallel to the longer line
x = 0.5*side_short
wr,hr = (x/sin_a,x/cos_a) if width_is_longer else (x/cos_a,x/sin_a)
else:
# fully constrained case: crop touches all 4 sides
cos_2a = cos_a*cos_a - sin_a*sin_a
wr,hr = (w*cos_a - h*sin_a)/cos_2a, (h*cos_a - w*sin_a)/cos_2a
return wr,hr
Here is a comparison of the function with the other solution:
>>> wl,hl = largest_rotated_rect(1500,500,math.radians(20))
>>> print (wl,hl),', area=",wl*hl
(828.2888697391496, 230.61639227890998) , area= 191016.990904
>>> wm,hm = rotatedRectWithMaxArea(1500,500,math.radians(20))
>>> print (wm,hm),", area=",wm*hm
(730.9511000407718, 266.044443118978) , area= 194465.478358
With angle angle
in [0,pi/2[
the bounding box of the rotated image (width w
, height h
) has these dimensions:
- width
w_bb = w*cos_a + h*sin_a
- height
h_bb = w*sin_a + h*cos_a
If w_r
, h_r
are the computed optimal width and height of the cropped image, then the insets from the bounding box are:
- in horizontal direction:
(w_bb-w_r)/2
- in vertical direction:
(h_bb-h_r)/2
Proof:
Looking for the axis aligned rectangle between two parallel lines that has maximal area is an optimization problem with one parameter, e.g. x
as in this figure:
Let s
denote the distance between the two parallel lines (it will turn out to be the shorter side of the rotated rectangle). Then the sides a
, b
of the sought-after rectangle have a constant ratio with x
, s-x
, resp., namely x = a sin α and (s-x) = b cos α:
So maximizing the area a*b
means maximizing x*(s-x)
. Because of “theorem of height” for right-angled triangles we know x*(s-x) = p*q = h*h
. Hence the maximal area is reached at x = s-x = s/2
, i.e. the two corners E, G between the parallel lines are on the mid-line:
This solution is only valid if this maximal rectangle fits into the rotated rectangle. Therefore the diagonal EG
must not be longer than the other side l
of the rotated rectangle. Since
EG = AF + DH = s/2*(cot α + tan α) = s/(2sin αcos α) = s/sin 2*α
we have the condition s ≤ lsin 2α, where s and l are the shorter and longer side of the rotated rectangle.
In case of s > lsin 2α the parameter x
must be smaller (than s/2) and s.t. all corners of the sought-after rectangle are each on a side of the rotated rectangle. This leads to the equation
x*cot α + (s-x)*tan α = l
giving x = sin α*(lcos α – ssin α)/cos 2*α. From a = x/sin α and b = (s-x)/cos α we get the above used formulas.