# Partition overlapping polygons

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. • The image shows a partition into 3 non-overlapping polygons. You can make it 2 by throwing away the green or blue edges of the intersections.
– mrk
Apr 4, 2014 at 12:31
• I would like to identify the different non-overlapping polygons (with the edges that form their boundaries).
Apr 4, 2014 at 12:38
• There are only two of them I guess. Can you give an example with a solution?
– mrk
Apr 4, 2014 at 12:41
• Here's another example of what I'd like to do: i.stack.imgur.com/Cjkas.png. The input is on the left; on the right, the domain is decomposed into non-overlapping polygons.
Apr 4, 2014 at 12:43

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.