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!

  • $\begingroup$ 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. $\endgroup$
    – mrk
    Apr 4, 2014 at 12:31
  • $\begingroup$ I would like to identify the different non-overlapping polygons (with the edges that form their boundaries). $\endgroup$
    – Link
    Apr 4, 2014 at 12:38
  • $\begingroup$ There are only two of them I guess. Can you give an example with a solution? $\endgroup$
    – mrk
    Apr 4, 2014 at 12:41
  • $\begingroup$ 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. $\endgroup$
    – Link
    Apr 4, 2014 at 12:43

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.