18
\$\begingroup\$

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 , 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
Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ will the input coordinates be ordered (cw/ccw)? \$\endgroup\$
    – asdf256
    Jan 6 at 12:04
  • \$\begingroup\$ @asdf256 Yes. You can use any order you find convenient. \$\endgroup\$
    – alephalpha
    Jan 6 at 13:11

4 Answers 4

Reset to default
9
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ How about [x,y,w,h,a] version of input? ;) \$\endgroup\$
    – lesobrod
    Jan 6 at 18:16
  • \$\begingroup\$ @lesobrod it wouldn't be a chore to just convert those to back to vertex coordinates with some trig :D \$\endgroup\$
    – asdf256
    Jan 7 at 3:20
7
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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/… \$\endgroup\$
    – alephalpha
    Jan 7 at 4:10
  • 1
    \$\begingroup\$ You can take the coordinates as a list of list. So the first answer can be 36 bytes: Area@RegionIntersection[Polygon/@#]& \$\endgroup\$
    – alephalpha
    Jan 7 at 4:14
  • \$\begingroup\$ @alephalpha, thank you for tips! Add and fix it \$\endgroup\$
    – lesobrod
    Jan 7 at 5:43
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – att
    Jan 7 at 6:32
  • \$\begingroup\$ @att Hope this much better, but i don't like single-letter names :p \$\endgroup\$
    – lesobrod
    Jan 7 at 12:25
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 198 bytes. Same formulas, just removed some unnecessary things that desmos adds by default. \$\endgroup\$
    – Bbrk24
    Apr 16 at 15:04
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.