Partition overlapping polygons

Question

On the following picture, we have overlapping polygons: we know the positions of vertices and the edges for each polygons, and the intersections are exactly known (vertices at the intersection are represented on the figure). Is it possible to 'partition' the domain spanned by the union of these polygons into 'disjoint' polygons (with contacts only at the boundary)? To be more precise, I'd like to associate to all edges the surfaces for which the edge is contained in its boundary.

Please advise if I'm not clear enough and thanks in advance for any suggestions!

Answer 1

First algorithm that came into my mind:

P = initial set of polygons
for every pair (p,q) of polygons in P
  if p intersects q
    remove p and q and insert the three polygons that make up p union q
repeat until P can't be grown anymore

If vertices have integer coordinates. You can use a matrix $M$ (initially $0$) and use the following algorithm:

for every polygon
  for every point p = (x,y) in the polygon
    M[y,x] += 1

A disjoint polygon is then a contiguous sub-area of the matrix. The entries in the sub-area are all equal.

One way to speed up the first algorithm is first to compute AABB's for each of the polygons and use a quadtree or some BSP data structure.