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

Question

问题:

我有一个用户生成的多边形(通过在屏幕上注册用户的触摸),它可以是简单的或复杂的(复杂意味着具有未知数量的交叉点)并且我希望有一个简单的多边形由原始多边形上的相同点产生,类似于轮廓或轮廓,如果你愿意.

可能的解决方案:

我发现了这个,但它是一个JavaScript解决方案,这是我需要的完美插图,但在ActionScript中!我不需要Path本身,这些点就足够了.你会怎么解决这个问题？

更新:

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

Answer 1

您描述的操作是联合.通常,计算一组多边形的并集有点复杂.有效和准确地这样做更复杂.iOS不为此操作提供公共API.

我建议您考虑使用现有的C或C++库来为您完成.这里有一些:

• Clipper(Boost许可证)
• Boost Geometry(Boost许可证)
• General Polygon Clipper(免费用于非商业用途;已经有Objective-C包装)

您可以从这些页面的链接或使用您最喜欢的搜索引擎找到其他内容.有用的搜索术语包括"多边形","几何体","联合"和"剪切".

UPDATE

我知道你只是绘制一个多边形.然而,至少在Clipper库的情况下,union操作可以满足您的要求:

白色背景上的多边形是我通过点击创建的星.它与自身相交.我使用Clipper的union操作在绿色背景上创建多边形.我将抽出的多边形作为主题传递,没有剪切多边形:

- (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存储库下载我自包含的测试应用程序.