如何在iOS中简化单个复杂的UIBezierPath多边形 [英] How to simplify a single complex UIBezierPath polygon in iOS

问题描述

问题：

我有一个用户生成的多边形（通过在屏幕上注册用户的触摸），它可以是简单的或复杂的（复杂意味着具有未知数量的交叉点）和我希望有一个简单的多边形，由原始多边形上的相同点产生，如果你愿意，可以像轮廓或轮廓一样。

可能的解决方案：

我找到了（Boost许可证）

函数，为星形示例生成相同的结果，可能代码较少。我不知道它为第二个例子（内部孔）产生了什么。我没试过。

你可以从这个github存储库。

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:

解决方案

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.

这篇关于如何在iOS中简化单个复杂的UIBezierPath多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！