If you do not care about predictable run time you could try by first splitting your polygons into unions of convex polygons and then pairwise computing the intersection between the sub-polygons.
This would give you a collection of convex polygons such that their union is exactly the intersection of your starting polygons.