Intersection area of two rotated rectangles

Question

Given two rectangles, which are possibly not in the orthogonal direction, find the area of their intersection.

enter image description here

Input

You may take the rectangles as input in one of the following ways:

• The coordinates of the four vertices of the rectangle. These coordinates are guaranteed to represent a rectangle.
• The coordinates of the center of the rectangle, the width, the height, and the angle of rotation.
• The coordinates of the center of the rectangle, half the width, half the height, and the angle of rotation.
• The coordinates of the four vertices of the unrotated rectangle, and the angle of rotation. Since the unrotated rectangle is in the orthogonal direction, its coordinates can be represented by four numbers instead of eight. You may choose to rotate about either the center of the rectangle or the origin.

The angle can be either in degrees or radians. It can be either counterclockwise or clockwise.

You don't need to take the two rectangles in the same way.

Output

The area of the intersection of the two rectangles.

The output must be within a relative or absolute error of \10ドル^{-3}\$ of the expected answer for the given test cases.

This means that, if the expected answer is \$x\$, and your answer is \$y\$, then \$y\$ must satisfy \$|x - y| \leq \max(10^{-3}, 10^{-3} x)\$.

This is code-golf, so the shortest code in bytes wins.

Test cases

In the test cases, the rectangles will be given in the format [x, y, w, h, a], where (x, y) is the center of the rectangle, w is the width, h is the height, and a is the angle of rotation in radians. The angle is measured counterclockwise from the positive x-axis.

[[0.0,0.0,1.0,1.0,0.0], [0.0,0.0,1.0,1.0,0.0]] -> 1.0
[[0.0,0.0,1.0,1.0,0.0], [0.0,0.0,1.0,1.0,0.785398]] -> 0.828427
[[-3.04363,2.24972,4.58546,9.13518,2.46245], [-3.2214,4.88133,9.71924,8.41894,-2.95077]] -> 31.9172
[[-0.121604,-0.968191,4.37972,3.76739,0.378918], [-2.64606,4.07074,5.22199,0.847033,-0.785007]] -> 0.0
[[-2.00903,-0.801126,9.90998,6.7441,-1.69896] ,[-2.6075,4.35779,4.29303,8.99664,-0.644758]] -> 14.5163
[[-3.29334,-1.24609,8.73904,3.86844,-2.90883], [-3.77132,-0.751654,1.14319,6.62548,0.806614]] -> 5.26269
[[3.74777,3.13039,1.94813,6.56605,1.53073], [1.20541,4.38287,5.16402,3.75463,-1.66412]] -> 4.89221
[[2.40846,1.71749,7.71957,0.416597,-2.4268], [-0.696347,-2.3767,5.75712,2.90767,3.05614]] -> 0.000584885
[[3.56139,-2.87304,8.19849,8.33166,1.00892], [3.03548,-2.46197,8.74573,7.43495,-2.88278]] -> 54.0515
[[3.49495,2.59436,8.45799,5.83319,0.365058], [3.02722,1.64742,1.14493,2.96577,-2.9405]] -> 3.3956

• asdf256: will the input coordinates be ordered (cw/ccw)?
• alephalpha: @asdf256 Yes. You can use any order you find convenient.

Answer 1

Python + Shapely, 88 bytes

lambda x,y:Polygon(x).intersection(Polygon(y)).area
from shapely.geometry import Polygon

Takes a list of ordered vertex coordinates for both rectangles (or any polygons) as input.

A solution using Shapely 2.0, but I'm working on golfing an awfully long solution which uses line-line intersection and the shoelace formula.

• lesobrod: How about [x,y,w,h,a] version of input? ;)
• asdf256: @lesobrod it wouldn't be a chore to just convert those to back to vertex coordinates with some trig :D

Answer 2

Mathematica (削除) 60 (削除ここまで) 36 or (削除) 222 (削除ここまで) 175 bytes

Pure coordinate input:

Area@RegionIntersection[Polygon/@#]&

Thanks to @alephalpha and @att!

{x,y,w,h,a} - input:

Area@RegionIntersection[Polygon/@((s=Sin@#5;c=Cos@#5;v1=#4s;v2=#3c;v3=#4c;v4=#3s;
.5{{v1+v2,v4-v3},{v2-v1,v3+v4},{-v1-v2,v3-v4},{v1-v2,-v3-v4}}+Table[{#1,#2},4])&@@@#)]&;

Expanded version self-explained:

Area@RegionIntersection[
 Polygon /@
 (
 With[
 {v1 = Sin@#[[5]] #[[4]],
 v2 = Cos@#[[5]] #[[3]],
 v3 = Cos@#[[5]] #[[4]],
 v4 = Sin@#[[5]] #[[3]]},
 .5 {{v1 + v2, v4 - v3}, {v2 - v1, v3 + v4 }, {- v1 - v2, 
 v3 - v4 }, {v1 - v2, -v3 - v4}} + 
 Table[{#[[1]], #[[2]]}, 4]] & /@ ##
 )
 ]&

A bit non-code golf, cause Area and RegionIntersection are extra-power built-ins. But this is working answer anyway =)

• alephalpha: You need to take input via function argument or Input[]. Storing the input in a predefined variable is not allowed. See this post on meta: codegolf.meta.stackexchange.com/questions/2447/…
• alephalpha: You can take the coordinates as a list of list. So the first answer can be 36 bytes: Area@RegionIntersection[Polygon/@#]&
• lesobrod: @alephalpha, thank you for tips! Add and fix it
• att: Save... a lot from the long version by #[[2]]->#2 etc. with @@@ instead of /@, removing the whitespace after the trigonometric expressions, single-letter variable names, removing With, ##-># for the sole argument.
• lesobrod: @att Hope this much better, but i don't like single-letter names :p

Answer 3

Desmos, 229 bytes (non-competing)

u(x)=\frac{\operatorname{sign}(x)+1}{2}
t(a,b,c,d,x,y)=u(c-abs((x-a.x)\cos(b)-(y-a.y)\sin(b)))u(d-abs((x-a.x)sin(b)+(y-a.y)cos(b)))
f(a,b,c,d,g,h,i,j)=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}t(a,b,c,d,x,y)t(g,h,i,j,x,y)dxdy

Try it online!

Takes input as center point, rotation angle (radians), half width, half height, and then the same for the second rectangle.

First we define u to be the step function, then we define t to take a rectangle and coordinates x, y, and using transformations and the step function return 1 if the point is in the rectangle and 0 if it isn't. Then for f we simply multiply t applied to each rectangle, giving us a function which is 1 in the intersection and 0 otherwise. The we simply integrate this over x and y and we have the area.

So why non-competing? It doesn't meet the accuracy requirement. The theory here is sound, and I'm not enough of an expert in Desmos to know the technical reasons it isn't accurate, but in general Desmos is only so good at integrals. You may think it has to do with the bounds being \$-\infty\$ to \$\infty\$, but I tried finite (\$-5\$ to \5ドル\$) bounds as well and it made no difference. I think if the requirement was \10ドル^{-2}\$, it would actually pass, but alas.

• Bbrk24: 198 bytes. Same formulas, just removed some unnecessary things that desmos adds by default.

Answer 4

MATLAB, 344 bytes

344 bytes, maybe golfed more.

R=@(r1,r2)polyshape((r1(3)/2*[-1 1 1 -1])'*cos(r1(5))-(r1(4)/2*[-1 -1 1 1])'*sin(r1(5))+r1(1), (r1(3)/2*[-1 1 1 -1])'*sin(r1(5))+(r1(4)/2*[-1 -1 1 1])'*cos(r1(5))+r1(2)).intersect(polyshape((r2(3)/2*[-1 1 1 -1])'*cos(r2(5))-(r2(4)/2*[-1 -1 1 1])'*sin(r2(5))+r2(1),(r2(3)/2*[-1 1 1 -1])'*sin(r2(5))+(r2(4)/2*[-1 -1 1 1])'*cos(r2(5))+r2(2))).area

---

Single file that can directly run:

%test_CGCC256396.m
R = @(r1, r2) polyshape((r1(3)/2*[-1 1 1 -1])'*cos(r1(5))-(r1(4)/2*[-1 -1 1 1])'*sin(r1(5))+r1(1), (r1(3)/2*[-1 1 1 -1])'*sin(r1(5))+(r1(4)/2*[-1 -1 1 1])'*cos(r1(5))+r1(2)).intersect(polyshape((r2(3)/2*[-1 1 1 -1])'*cos(r2(5))-(r2(4)/2*[-1 -1 1 1])'*sin(r2(5))+r2(1), (r2(3)/2*[-1 1 1 -1])'*sin(r2(5))+(r2(4)/2*[-1 -1 1 1])'*cos(r2(5))+r2(2))).area;
rectangle_intersection = @(rect1, rect2) R(rect1, rect2);
rectangles = [
 [0.0,0.0,1.0,1.0,0.0],
 [0.0,0.0,1.0,1.0,0.0],
 [0.0,0.0,1.0,1.0,0.0],
 [0.0,0.0,1.0,1.0,0.785398],
 [-3.04363,2.24972,4.58546,9.13518,2.46245],
 [-3.2214,4.88133,9.71924,8.41894,-2.95077],
 [-0.121604,-0.968191,4.37972,3.76739,0.378918],
 [-2.64606,4.07074,5.22199,0.847033,-0.785007],
 [-2.00903,-0.801126,9.90998,6.7441,-1.69896] ,
 [-2.6075,4.35779,4.29303,8.99664,-0.644758],
 [-3.29334,-1.24609,8.73904,3.86844,-2.90883],
 [-3.77132,-0.751654,1.14319,6.62548,0.806614],
 [3.74777,3.13039,1.94813,6.56605,1.53073],
 [1.20541,4.38287,5.16402,3.75463,-1.66412],
 [2.40846,1.71749,7.71957,0.416597,-2.4268],
 [-0.696347,-2.3767,5.75712,2.90767,3.05614],
 [3.56139,-2.87304,8.19849,8.33166,1.00892],
 [3.03548,-2.46197,8.74573,7.43495,-2.88278],
 [3.49495,2.59436,8.45799,5.83319,0.365058],
 [3.02722,1.64742,1.14493,2.96577,-2.9405]
 ];
for i = 1:2:size(rectangles,1)
 rect1 = rectangles(i,:);
 rect2 = rectangles(i+1,:);
 area = rectangle_intersection(rect1, rect2);
 fprintf("Intersection area of rectangle %d and %d: %f\n", i, i+1, area);
end

Intersection area of rectangle 1 and 2: 1.000000
Intersection area of rectangle 3 and 4: 0.828427
Intersection area of rectangle 5 and 6: 31.917167
Intersection area of rectangle 7 and 8: 0.000000
Intersection area of rectangle 9 and 10: 14.516304
Intersection area of rectangle 11 and 12: 5.262695
Intersection area of rectangle 13 and 14: 4.892207
Intersection area of rectangle 15 and 16: 0.000585
Intersection area of rectangle 17 and 18: 54.051499
Intersection area of rectangle 19 and 20: 3.395599

---

Ungolfed version, with detailed code comment

function area = rectangle_intersection(rect1, rect2)
 % rect1 and rect2 are arrays of the form [x, y, w, h, a]
 % where (x, y) is the center of the rectangle, w is the width,
 % h is the height, and a is the angle of rotation in radians.
 % create polygons representing the rectangles
 poly1 = create_polygon(rect1);
 poly2 = create_polygon(rect2);
 % find the intersection of the polygons
 poly_intersect = intersect(poly1, poly2);
 % calculate the area of the intersection
 area = poly_intersect.area;
end
function poly = create_polygon(rect)
 % create a polygon representing the given rectangle
 x = rect(1); y = rect(2); w = rect(3); h = rect(4); a = rect(5);
 % calculate the coordinates of the corners of the rectangle
 corners = [-w/2 -h/2; w/2 -h/2; w/2 h/2; -w/2 h/2];
 % rotate the corners by the angle a
 rot_mat = [cos(a) sin(a); -sin(a) cos(a)];
 corners = corners * rot_mat;
 % translate the corners to the center of the rectangle
 corners(:,1) = corners(:,1) + x;
 corners(:,2) = corners(:,2) + y;
 % create the polygon
 poly = polyshape(corners(:,1), corners(:,2));
end