二分法求不规则闭合路径与线段的交点

本文中约定 :

路径 : 不规则闭合路径
线段 : 一个端点在路径内，另外一端点在路径外的线段
交点 : 路径和线段的交点

9月份某个中午和同事闲聊过程中，突然想到一种简单算法来求线段与路径的交点。

算法

核心就是二分法。通过不断二分线段，来求这条线段与路径的交点。每次二分线段之后取和路径相交的那一段线段继续二分。算法会很快收敛，迭代几次便可以得到一个高精度的交点。

如何判断二分之后哪条子线段与路径相交？判断这个子线段一个端点在路径内，另一个在路径外即可。

计算函数如下,

CGPoint GeometryIntersectionOfPathAndLine(CGPoint innerPoint, CGPoint outerPoint, CGPathRef path)
{
    CGFloat precision = 0.1;
    
    CGPoint middlePoint = CGPointMake((innerPoint.x + outerPoint.x) * 0.5,
                                      (innerPoint.y + outerPoint.y) * 0.5);
    
    BOOL middleIn = CGPathContainsPoint(path, NULL, middlePoint, YES);
    
    CGPoint validPoint = middleIn ? outerPoint : innerPoint;
    
    if (fabs(validPoint.x - middlePoint.x) < precision &&
        fabs(validPoint.y - middlePoint.y) < precision) {
        return middlePoint;
    }
    
    return GeometryIntersectionOfPathAndLine(middleIn ? middlePoint : validPoint,
                                             middleIn ? validPoint : middlePoint,
                                             path);
}