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

Question

问题：

我有一个由用户在屏幕上注册的多边形，可以是简单的，也可以是复杂的（复杂意味着具有未知数量的交点），我希望从原始多边形中得到一个简单的多边形，类似于轮廓或者等高线。

可能的解决方案：

我找到了this，但它是一个JavaScript解决方案，this是我需要的完美示例，但它是使用ActionScript编写的！我不需要路径本身，只需要点即可。你会如何解决这个问题？

更新：

当我进一步查看时，我看到有些人建议使用凸包算法处理这些点，但是，凸包在这里并不是答案，因为如果我没错，结果将如下所示：

- M. Porooshani

---

你尝试过将JavaScript的解决方案翻译成Objective-C吗？ - Martin R

我本来想建议类似于其他问题的答案，但我的唯一警告是确保您从其他路径中不包含的一个点开始。我建议您尝试该算法，如果遇到障碍，请发布您的尝试并我们会看看能否帮忙。 - Rob

@Rob，我知道点的顺序，但是实现该算法需要一些额外的工具，例如UIBezierPath无法提供！ - M. Porooshani

同意，UIBezierPath 不会为您完成任何此类操作。您只会使用它来渲染您构建的最终路径。但是您需要自己编写相当多的例程：您需要一个“查找两条线段之间的交点”例程，然后有了这个，您可以编写一个“从找到的交点数组中选择最近的交点”的例程。您可能还需要一个“计算三个点之间的角度”的算法。但是，有了这些工具，您就可以实现该算法。 - Rob

@Rob 我已经有它们了，但我不太清楚该怎么做！我想用非零样式填充多边形，然后将其转换为新轮廓，但我不确定是否可行！ - M. Porooshani

Answer 1

您所描述的操作是联合。通常，计算一组多边形的联合相当复杂。以高效和准确的方式执行此操作更加复杂。iOS没有提供此操作的公共API。

我建议您考虑使用现有的C或C ++库来执行此操作。以下是一些：

• Clipper（Boost许可证）
• Boost Geometry（Boost许可证）
• 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函数，可以用更少的代码生成与星形示例相同的结果。我不知道它对于第二个带有内部孔的示例会生成什么。我没有尝试过。

您可以从此Github存储库下载我的自包含测试应用程序。

- rob mayoff

---

谢谢Rob，但是看起来你没有仔细阅读问题，这是一个单一的多边形，而Union适用于多个多边形。 - M. Porooshani

那是一个很棒的答案，Rob。我会尽快给你奖励金。再次感谢。 - M. Porooshani

我已经测试了您的拒绝功能，对于更复杂的形状仍然无法胜任。但它确实做到了我想要的。 - M. Porooshani

恭喜你，Rob，这是一个很棒的解决方案。我认为它应该成为维基条目，但只有你愿意的话。 - M. Porooshani

Answer 2

要使用JavaScript代码，您可以查看this答案：

在iOS 7中引入的JavascriptCore框架中的Objective-C接口允许从Javascript调用Objective-C方法。有关这些功能的详细介绍，请参阅苹果开发人员网络上2013 WWDC介绍“将JavaScript集成到本地应用程序中”的会话：https://developer.apple.com/videos/wwdc/2013/?id=615

它提到了JS-> Objective-C，但JSCore也可以反过来工作。

否则，正如有人建议的那样，将JS代码“翻译”应该相当容易，因为它只是数学计算。

- Rivera

---

我应该提到，我需要iOS 6+的解决方案。无论如何，我会尝试并告诉你结果。 - M. Porooshani

那么也许你应该只是“翻译”它。 - Rivera

Answer 3

稍加思考：

1. 找到最左边的顶点。它肯定在边界上。从那里开始；
2. 沿着当前边缘朝下一个列出的顶点方向查看；
3. 检查是否有其他边与您正在查看的边相交；
4. 如果是，则找到当前位置前面的第一个顶点并移动到该顶点；
5. 使用您刚刚转换到的边从（2）重复；
6. 继续，直到回到（1）处的顶点。

（请参见关于从UIBezierPath中获取路径的早期错误评论的注释）

- Tommy

---

要查询 UIBezierPath 的几何形状，您可以获取它的 CGPath 并使用 CGPathApply 遍历路径元素。 - Nikolai Ruhe