Conceptually, if you don't care about speed, take an algorithm that decomposes $N$-gons into $N-2$ "disjoint" (modulo common edges) triangles -- for convex polygons this is trivial -- and then, for each pair of triangles (one from $P1$ and one from $P2$), apply an algorithm that computes the overlap, if any, of two triangles. This shows the complexity is at worst $O(mn)$, at least in the convex case. One question might be, how does this compare with the approaches in the answers already given by meij and Stephen Sturgeon?

**Added later**: It occurs to me I might be under a misimpression as to how the polygons are being specified. I am assuming that to "have the boundaries" means, in effect, that you have a listing of the vertices as you go around the boundary. If it means something else, then what I described above requires a prefatory step that produces such a list. (Also, if the OP really wants the overlaps of the convex hulls of $P1$ and $P2$, then lists of the hulls' vertices need to be ascertained.)