ios - 如何在 iOS 中简化单个复杂的 UIBezierPath 多边形

Question

问题:

我有一个用户生成的多边形(通过在屏幕上注册用户的触摸)，它可以是简单的也可以是复杂的(复杂意味着具有未知数量的交叉点)并且我想要一个简单的多边形，该多边形是由原始多边形上的相同点产生的，如果您愿意，可以使用轮廓或轮廓之类的东西。

可能的解决方案:

我找到了 this , 但它是一个 JavaScript 解决方案和 this完美地说明了我需要什么，但在 ActionScript 中!我不需要 Path 本身，这些点就足够了。你会如何处理这样的问题？

更新:

当我进一步观察时，我看到一些人建议解决方案是在点上使用Convex Hull 算法，但是，凸包不是答案在这里，因为如果我是对的，结果将如下:

Answer 1

您所描述的操作是一个联合。通常，计算一组多边形的并集有些复杂。高效、准确地做到这一点更加复杂。 iOS 不为此操作提供公共(public) API。

我建议您考虑使用现有的 C 或 C++ 库来为您做这件事。这里有一些:

• Clipper (提升许可证)
• Boost Geometry (提升许可证)
• General Polygon Clipper (非商业用途免费；已有 Objective-C 包装器)

您可以从这些页面的链接或使用您最喜欢的搜索引擎找到其他内容。有用的搜索词包括“多边形”、“几何”、“并集”和“剪裁”。

更新

我知道您只是在绘制一个多边形。尽管如此，至少在 Clipper 库的情况下，联合操作可以满足您的要求:

白色背景上的多边形是我通过点击创建的星星。它与自身相交。我使用 Clipper 的联合操作在绿色背景上创建多边形。我将截取的多边形作为主题传递，没有剪辑多边形:

- (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;
}

另一方面，给定一个更复杂的输入多边形，您可能希望通过多种方式对其进行修改:

简单的(单个)并集返回一个带有孔洞的多边形。如果您不希望输出中出现空洞，则需要采用初始并集输出的各个循环(子路径)，以相同的方式对它们进行定向，然后对所有定向循环进行第二次并集。这就是我在橙色背景上计算“深度联合”多边形的方式:

- (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 还有一个 SimplifyPolygon为 star 示例产生相同结果的函数，也许代码更少。我不知道第二个示例(带有内部孔)产生了什么。我没试过。

您可以从 this github repository 下载我的独立测试应用程序.