Q:

How to find area of intersection of two moving polygons?

We have two non-convex polygons:
M: $(x^1, y^1), (x^2, y^2),..., (x^m, y^m)$;
N: $(x^1, y^1), (x^2, y^2),..., (x^n, y^n)$;
They move at speeds:
$v^M=(v^M_x, v^M_y)$;
$v^N=(v^N_x, v^N_y)$;  
How to find moment of time t where area of intersection is maximum?

A:

You can find the time of maximum area of intersection by setting the first polygon's motion vector to zero and the second polygon's motion vector to
$v^N - v^M.$
So now we have reduced the problem to a case where only one polygon is moving. Transform all coordinates so that the motion is in the direction of the positive $x$ axis.
Take the set of all vertices of both polygons.
Through each vertex, construct a line parallel to the $x$ axis.
Use these lines to partition each polygon into trapezoids.
(Some of the trapezoids may be triangles, that is, degenerate trapezoids in which one base has zero length. Since the polygons were initially not convex,
there may be multiple trapezoids from the same polygon between two adjacent lines.)
Now consider the trapezoids in which the second polygon is partitioned,
all moving at the same speed parallel to their bases.
If we consider just one of these trapezoids along with one of the trapezoids of the first polygon,
the area of intersection of the two trapezoids is a piecewise quadratic function of time,
and the pieces of that function begin and end at times when a vertex of one trapezoid coincides with a vertex of the other trapezoid, which times can easily be calculated.
There are four of these times, and depending on the sequence in which they occur (which pairs of coordinates coincided before which other pairs of coordinates) there are just a few cases for deciding which quadratic function represents the area between those times.
Now take the sum of the functions for all pairs of trapezoids (one from the first polygon, one from the second) that can have non-zero area of intersection (that is, their bases are on the same pair of parallel lines).
The result is a single piecewise quadratic function.
Maximize that function.

