The operation you are describing is a union. Generally, computing the union of a set of polygons is somewhat complicated. Doing so efficiently and accurately is more complicated. iOS doesn't provide a public API for this operation.
I suggest you look into using an existing C or C++ library to do it for you. Here are some:
There are others you can find from links off of those pages or using your favorite search engine. Useful search terms include “polygon”, “geometry”, “union”, and “clipping”.
UPDATE
I understand that you're just drawing one polygon. Nevertheless, in the case of the Clipper library at least, the union operation does what you're asking for:
The polygon on the white background is the star I created by tapping. It intersects itself. I used Clipper's union operation to create the polygon on the green background. I passed the tapped-out polygon as the subject with no clip polygons:
- (UIBezierPath *)pathWithManyPoints:(CGPoint const *)points count:(NSUInteger)count {
Path subject;
for (NSUInteger i = 0; i < count; ++i) {
subject << IntPoint(points[i].x, points[i].y);
}
Clipper clipper;
clipper.AddPath(subject, ptSubject, true);
Paths solutions;
clipper.Execute(ctUnion, solutions, pftNonZero, pftNonZero);
UIBezierPath *path = [UIBezierPath bezierPath];
for (size_t i = 0; i < solutions.size(); ++i) {
Path& solution = solutions[i];
if (solution.size() > 0) {
[path moveToPoint:cgPointWithIntPoint(solution[0])];
for (size_t j = 1; j < solution.size(); ++j) {
[path addLineToPoint:cgPointWithIntPoint(solution[j])];
}
[path closePath];
}
}
return path;
}
On the other hand, given a more complex input polygon, there are a couple of ways you might want to modify it:
The simple (single) union gives you back a polygon with a hole in it. If you want no holes in the output, you need to take the individual loops (subpaths) output by the initial union, orient them all the same way, and then take a second union of all the oriented loops. That's how I computed the “deep union” polygon on the orange background:
- (UIBezierPath *)pathWithManyPoints:(CGPoint const *)points count:(NSUInteger)count {
Path subject;
for (NSUInteger i = 0; i < count; ++i) {
subject << IntPoint(points[i].x, points[i].y);
}
Clipper clipper;
clipper.AddPath(subject, ptSubject, true);
Paths intermediateSolutions;
clipper.Execute(ctUnion, intermediateSolutions, pftNonZero, pftNonZero);
clipper.Clear();
for (size_t i = 0; i < intermediateSolutions.size(); ++i) {
if (Orientation(intermediateSolutions[i])) {
reverse(intermediateSolutions[i]);
}
}
clipper.AddPaths(intermediateSolutions, ptSubject, true);
Paths solutions;
clipper.Execute(ctUnion, solutions, pftNonZero, pftNonZero);
UIBezierPath *path = [UIBezierPath bezierPath];
for (size_t i = 0; i < solutions.size(); ++i) {
Path& solution = solutions[i];
if (solution.size() > 0) {
[path moveToPoint:cgPointWithIntPoint(solution[0])];
for (size_t j = 1; j < solution.size(); ++j) {
[path addLineToPoint:cgPointWithIntPoint(solution[j])];
}
[path closePath];
}
}
return path;
}
Clipper also has a SimplifyPolygon function that produces the same result for the star example, perhaps with less code. I don't know what it produces for the second example (with the interior hole). I didn't try it.
You can download my self-contained test app from this github repository.
