How to intersect multiple polygons?

Question

I am looking for an algorithm with the following input and output:

Input: A set of polygons in a plane. E.g. P1...Pn and S. (P1...Pn might be concave, S is convex.)

Output: The area of theset of polygons in this plane that equals the difference of S and the union of P1...Pn.

I found algorithms to intersect or merge TWO polygons. But since each of those operations might produce several polygons I createt tons of polygons if I did it naively.

So: How to handle the intersection of multiple polygons?

It would be ok, if all polygons are connected together since only the area is what I am after. My thought was to use directed polygons to simulate holes but then I again have the problem to find out if I have a "minimal representation" as n could blow up. [Do you understand what I am talking about? It's quite strange...)

Answer 1

You could throw all edges together into a sweep line algorithm. It may not be optimal (?) but at least you will get the minimal representation you are looking for.

Answer 2

One solution is to convert each polygon into a bunch of triangles. Once you do that it is fairly easy to find union/intersection/difference between a set of areas since you can perform the same functions trivially on a triangle (result on two triangles may include up to 6 triangles).

Answer 3

The most straightforward approach would be decomposing your concave polygons into convex ones. Then intersecting two convex polygons is almost trivial.