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

Classic point in polygon problem. Remove all the points in each polygon that return 1 referencing the other polygon:

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
  int i, j, c = 0;
  for (i = 0, j = npol-1; i < npol; j = i++) {
    if ((((yp[i] <= y) && (y < yp[j])) ||
         ((yp[j] <= y) && (y < yp[i]))) &&
        (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
      c = !c;
  }
  return c;
}

Combine the two paths with the removed points.

Pseudo code for the whole procedure:

define starPoly with 10 points
define simplePoly with 7 points

for each point in starPoly
    if ( pnpoly( 7, simplePoly.Xs[], simplePoly.Ys[], point.x, point.y ) == 0 )
        clipedStarPoly += point;

for each point in simplePoly
    if ( pnpoly( 10, starPoly.Xs[], starPoly.Ys[], point.x, point.y ) == 0 )
        clipedSimplePoly += point;

for each point in clipedStarPoly
    solutionPoly += point;

for each point in clipedSimplePoly
    solutionPoly += point;

solutionPoly += solutionPoly.point[0]

If you don't think you will have to play with the endpoints of the clipped polys you can simply build the solution poly directly out of the point tests.

You may want to use ray tracing for the point in poly test, try looking at this page

Answer 2

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.

Answer 3

Use CGPathAddPath. Super easy to use.

Answer 4

It's not enough to simply union two sets of points. In order to determine the combined polygons, you would need to do the following. Sorry I only have pseudocode, I only just started looking at this problem.

We will consider the two polygons to be A and B. It does not matter which is which.

• Move around polygon A looking for any point that is NOT inside polygon B.
• Add this point to the polygon.
• Continue around the polygon, testing and adding each point in turn.
• When you discover a point that IS inside polygon B, look at the line between it and the previous point.
• Find out which line on polygon B intersects with this line.
• Determine the point of intersection between these two lines and add it to the polygon.
• Determine which of the two points that define the intersecting line belonging to polygon B is NOT inside polygon A and add that to the new polygon.
• Determine which direction around polygon B you need to go in order that the next point will NOT be the one on the other end of the line of intersection and add it.
• Repeat from 3, except using polygon B instead of polygon A
• Continue until you reach the point you started from, swapping between polygons as necessary.

Note that this solution is only acceptable for straight-sided polygons. Where a bezier path is concerned, it becomes a lot more difficult to calculate the points of intersection, not to mention the complexities of combining smooth corners with sharp corners, or curves with straight line segments.