How to simplify a single complex UIBezierPath polygon in iOS

Question

Problem:

I have a user generated polygon (via registering user's touches on screen) which can be simple or complex (complex means having unknown number of intersections) and I want to have a simple polygon resulting from the same points on the original polygon, something like an outline or a contour if you will.

Possible solutions:

I have found this, but it is a JavaScript solution and this is a perfect illustration of what I need but in ActionScript! I don't need the Path itself, the points will suffice. How would you approach such problem?

Update:

As I was looking further around, I have seen a few people suggesting that the solution is using a Convex Hull algorithm on the points, but, convex hull is not the answer here because if I'm right the result will be as follows:

Answer 1

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:

• Clipper (Boost license)
• Boost Geometry (Boost license)
• General Polygon Clipper (Free for non-commercial use; has an Objective-C wrapper already)

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.

Answer 2

To use the JavaScript code you can check this answer:

The Objective-C interface in the JavascriptCore framework introduced with iOS 7 permits calling Objective-C methods from Javascript. For a great intro to these features, check out the 2013 WWDC introduction "Integrating JavaScript into Native Apps" session on Apple's developer network: https://developer.apple.com/videos/wwdc/2013/?id=615

It mentions JS->Objective-C but JSCore also works the other way around.

Otherwise as someone suggested it should be fairly easy to "translate" the JS code as it would just be mathematical calculations.

Answer 3

With a little thought:

1. find the leftmost vertex. It's definitely on the boundary. Start there;
2. look along the current edge towards the next listed vertex;
3. check if any of the other edges intersect the one you're looking along;
4. if so then find the first vertex in front of your current position and move to it;
5. repeat from (2) with the edge you just transitioned onto;
6. continue until you get back to the vertex at (1).

(and see the comment re: an erroneous earlier comment I'd made about getting the path out of a UIBezierPath)