k-way triangle set intersection and triangulation

Question

If we have K sets of potentially overlapping triangles, what is a computationally efficient way of computing a new, non-overlapping set of triangles?

For example, consider this problem:

Here we have 3 triangle sets A, B, C, with some mutual overlap, and wish to obtain the non-overlapping sets A', B', C', AB, AC, BC, ABC, where for example the triangles in AC would contain the surfaces where there is exclusive overlap among A and C; and A' would contain the surfaces of A which do not overlap any other set.

Answer 1

I (also) propose a two step approach.

1. Find the intersection points of all triangle sides.

As pointed out in the comments, this is a well-researched problem, typically approached with line sweep methods. Here is a very nice overview, look especially at the Bentley-Ottmann algorithm.

2. Triangulate with Constrained Delaunay.

I think Polygon Triangulation as suggested by @Claudiu cannot solve your problem as it cannot guarantee that all original edges are included. Therefore, I suggest you look at Constrained Delaunay triangulations. These allow you to specify edges that must be included in your triangulation, even if they would not be included in an unconstrained Delaunay or polygon triangulation. Furthermore, there are implementations that allow you to specify a non-convex border of your triangulation outside of which no triangles are generated. This also seems to be a requirement in your case.

Implementing Constrained Delaunay is non-trivial. There is however, a somewhat dated but very nice C implementation of available from a CMU researcher (including a command line tool). See here for the theory of this specific algorithm. This algorithm also supports specification of a border. Note that the linked algorithm can do more than just Constrained Delaunay (namely quality mesh generation), but it can be configured not to add new points, which amounts to Constrained Delaunay.

Edit See comments for another implementation.