Combining Intersecting CGPaths on iOS

Question

I have a problem in an app I'm working on. Say I have two CGPaths that are fairly complex and I add them both to a CGMutablePath (thus combining them). Well, where the two paths intersect there will be points inside of each other. I want to eliminate those inside points and essentially draw the outside or outline of the path. I am having difficulty figuring out how I would go about this.

Edit: Here's an example of what I am talking about. The blue and red boxes represent points along the CGPaths. The red boxes are the points that are within both paths. I would like to somehow eliminate the red points and redraw just the outline of the path.

Answer 1

What you are describing is the union of the paths' interiors.

If your paths contain curves, this is a hard problem.

However, your example shows only straight line segments, so I will assume you only care about paths that solely contain straight line segments.

In that case, you want a polygon union function. This sort of algorithm is pretty basic in the field known as “computational geometry”. I don't know of any Objective-C-specific implementation of polygon union. You might be able to find a pure C library, but it's much easier to find a C++ library. You can use C++ if you change your file extension from .m to .mm. Here are some C++ libraries that can compute the union of polygons:

• Clipper
• GEOS - see Polygon::Union
• CGAL - see 2D Regularized Boolean Set-Operations
• boost geometry - see union_

Note that in all cases, you'll need to use CGPathApply to extract the vertices of your path, if you don't already have them in another format.