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

问题：

我有一个用户生成的多边形（通过在屏幕上注册用户的触摸），可以是简单的或复杂的（复杂的手段具有未知数量的交点），我想有一个简单的多边形产生于原多边形相同的点，就像轮廓或轮廓，如果你愿意。

可能的解决scheme：

我已经find了这个 ，但它是一个JavaScript解决scheme， 这是一个完美的例子，我需要什么，但在ActionScript！ 我不需要path本身，这些点就足够了。 你会如何解决这个问题？

更新：

当我进一步观察的时候，我看到有几个人认为解决scheme在点上使用凸包algorithm，但是凸包不是这里的答案，因为如果我是正确的，结果如下：

Answer 1

你所描述的操作是一个联合 。 一般来说，计算一组多边形的联合有些复杂。 这样做高效，准确是比较复杂的。 iOS不提供此操作的公共API。

我build议你看看使用现有的C或C ++库来为你做。 这里有一些：

• Clipper （Boost许可证）
• 提升几何 （提升许可证）
• General Polygon Clipper （免费用于非商业用途;已经有Objective-C包装）

还有其他人可以从这些网页的链接中find或使用您最喜爱的search引擎。 有用的search词包括“多边形”，“几何”，“联合”和“裁剪”。

UPDATE

我明白你只是绘制一个多边形。 尽pipe如此，至less在Clipper库的情况下，union操作完成了你所要求的操作：

白色背景上的多边形是我通过点击创build的明星。 它相交。 我使用Clipper的联合操作在绿色背景上创build多边形。 我通过挖掘出的多边形作为没有剪辑多边形的主题：

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

另一方面，给定一个更复杂的input多边形，有几种方法可能需要修改它：

简单的（单个）联合给你回一个有洞的多边形。 如果输出中没有空洞，则需要将初始联合输出的单个循环（子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函数，它为星形例子产生相同的结果，可能代码less。 我不知道它是如何产生的第二个例子（与内部孔）。 我没有尝试。

你可以从这个github仓库下载我自包含的testing应用程序。

Answer 2

要使用JavaScript代码，你可以检查这个答案：

iOS 7引入的JavascriptCore框架中的Objective-C接口允许从Javascript调用Objective-C方法。 要了解这些function的最佳介绍，请查看苹果开发人员networking2013年WWDC简介“将JavaScript集成到原生应用程序”会话： https ： //developer.apple.com/videos/wwdc/2013/？id = 615

它提到了JS-> Objective-C，但是JSCore也是相反的。

否则，正如有人build议，应该很容易“翻译”JS代码，因为它只是math计算。

Answer 3

有一点想法：

1. find最左边的顶点。 这绝对是在边界上。 从那里开始;
2. 沿着当前边缘看下一个列出的顶点;
3. 检查是否有任何其他的边缘与你正在寻找的边缘相交;
4. 如果是的话，find当前位置前的第一个顶点并移动到它;
5. 从（2）重复你刚过渡到的边缘;
6. 继续下去，直到回到（1）的顶点。

（并看到评论：我错误地提出了一条关于从UIBezierPath获得path的错误评论）