Two rectangles on a plane

Question

In the last few days I try to solve this problem. I even have the solution but I can't figure it out. Can someone help me?

Here the problem:

You are given two rectangles on a plane. The centers of both rectangles are located in the origin of coordinates (meaning the center of the rectangle's symmetry). The first rectangle's sides are parallel to the coordinate axes: the length of the side that is parallel to the Ox axis, equals w, the length of the side that is parallel to the Oy axis, equals h. The second rectangle can be obtained by rotating the first rectangle relative to the origin of coordinates by angle α.

Example: http://i.imgur.com/qi1WQVq.png

Your task is to find the area of the region which belongs to both given rectangles. This region is shaded in the picture.

Input The first line contains three integers w, h, α (1 ≤ w, h ≤ 106; 0 ≤ α ≤ 180). Angle α is given in degrees.

Output In a single line print a real number — the area of the region which belongs to both given rectangles.

The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Sample test(s)

input 1 1 45 output 0.828427125

input 6 4 30 output 19.668384925

Here a possible implementation:

<?php
list($w, $h, $alphaInt) = explode(' ', '34989 23482 180');

if ($alphaInt == 0 || $alphaInt == 180) {
  $res = $h * $w;
}
else if ($alphaInt == 90) {
  $res = $h * $h;
}
else {
  if ($alphaInt > 90) $alphaInt = 180 - $alphaInt;

  $alpha = $alphaInt / 180.0 * M_PI;
  //echo '$alpha:' . $alpha . "\n";

  $cos = cos($alpha);
  $sin = sin($alpha);
  //echo '$cos:  ' . $cos . "\n";
  //echo '$sin:  ' . $sin . "\n";

  $c = $w / 2 * $cos + $h / 2 * $sin - $w / 2;
  //echo '$c:    ' . $c . "\n";

  $r1 = $c / $cos;
  $r2 = $c / $sin;
  //echo '$r1:   ' . $r1 . "\n";
  //echo '$r2:   ' . $r2 . "\n";

  $c = $w / 2 * $sin + $h / 2 * $cos - $h / 2;
  //echo '$c:    ' . $c . "\n";

  $r3 = $c / $cos;
  $r4 = $c / $sin;
  //echo '$r3:   ' . $r3 . "\n";
  //echo '$r4:   ' . $r4 . "\n";

  if ($r1 < 0 || $r2 < 0 || $r3 < 0 || $r4 < 0) {
    $res = $h * $h / $sin; //$res = $w * $w / $cos;
  }
  else {
    $res = $h * $w - $r1 * $r2 - $r3 * $r4;
  }
}

echo '$res:  ' . $res . "\n";

Answer 1

Small alpha

When w*sin(alpha) < h*(1+cos(alpha)) (i.e., before the vertices of the new rectangle meet the vertices of the old one for the first time), the area of the intersection is the area of the original rectangle (w * h) minus 4 triangles (2 pairs of identical ones). Let the bigger triangle have hypotenuse a and the smaller hypotenuse b, then the area is

A = w * h - a*a*cos(alpha)*sin(alpha) - b*b*cos(alpha)*sin(alpha)

The sides of the original rectangle satisfy a system of equations:

a + a * cos(alpha) + b * sin(alpha) = w
a * sin(alpha) + b + b * cos(alpha) = h

Using the half-angle formulas,

a * cos(alpha/2) + b * sin(alpha/2) = w/(2*cos(alpha/2))
a * sin(alpha/2) + b * cos(alpha/2) = h/(2*cos(alpha/2))

thus (the matrix on the LHS is a rotation!)

a^2 + b^2 = (w^2 + h^2) / (2*cos(alpha/2))^2

and

A = h * w - (w^2 + h^2) * cos(alpha)* sin(alpha) / (2*cos(alpha/2))^2

(this can be simplified further a little bit)

Bigger alpha

When alpha is bigger (but still alpha<pi/2), the intersection is a parallelogram (actually, a rhombus) whose 2 altitudes are h and 4 sides h/sin(alpha) and the area is, thus, h*h/sin(alpha) (yes, it does not depend on w!)

Other alpha

Use symmetry to reduce alpha to [0;pi/2] and use one of the two cases above.

Answer 2

You might try describing both rectangles as solutions to a system of four linear insqualities. The set of points in their intersection is the set of solutions to both sets of linear inequalities.

You want the area of that set of solutions. You can find all points at which at least two of your eight inequalities are tight. Filter out those that don't satisfy all of the inequalities. Then take their convex hull using Graham's scan and compute the area using the surveyor's formula.

This method works to find the intersection of any two convex polygons. Slightly modified, it generalises (in the form of Fourier-Motzkin elimination and the double description method for computing the intersection and determinants for volume calculation) to convex polyhedra in any dimension.