檢測點是否在SVG路徑中

Question

我試圖檢測給定點是否在Objective-C中的封閉SVG路徑內。我很難搞清楚如何做數學。

我有一個路徑的座標，我想確定一個隨機點在路徑的內部還是外部。

這裏有一個路徑的座標的一個例子：

"M673 460 c2 0 4 -1 5 -2 1 -1 2 -2 2 -4 0 -2 0 -3 0 -3 0 0 -3 1 -5 1 -3 1 -5 2 -5 3 0 1 0 3 0 4 1 0 2 1 3 1z:" 

我知道了CoreGraphics中的containsPoint:方法，但我想避免使用此方法。

如何通過編寫我自己的方法來做到這一點？

編輯：

我試圖避免containsPoint:因爲功能似乎使用時的一些座標/路徑崩潰。當它崩潰時它看起來非常隨機，當它不崩潰時它看起來很隨機。

下面是路徑的一些示例中containsPoint:使得應用程序崩潰：

"M661 446 c1 -1 3 -1 4 -1 1 -1 2 -2 2 -4 0 -2 0 -2 -2 -2 0 1 -2 1 -3 1 -2 0 -3 1 -3 2 0 1 0 2 0 3 0 0 1 1 2 1z" 
"M535 460 c0 0 1 -1 1 -2 1 -2 0 -3 -1 -3 0 0 -1 0 -2 1 0 1 0 2 0 3 1 0 1 1 2 1z" 

Xcode的場所與和在裝配EXC_BAD_ACCESS由以下兩個功能：get_y_inflections和get_cubic_coefficients。

編輯2：

我發佈了new question有關containsPoint:問題。

Answer 1

所以，當我從曲線路徑需要一個多邊形/插值自己，我可能對您的問題以及解決方案：

兩個「公共」功能：

CGPathRef CGPathCreatePolygonPath(CGPathRef path, int quality);

創建具有僅線路元素的路徑，質量是一個曲線被分成

BOOL CGPathContainsPointInterpolated(CGPathRef path, const CGAffineTransform *m, CGPoint point, bool eoFill, int quality);

段的數量0

CGPathContainsPoint和Interpolation是否在一個步驟中，質量又是一條曲線分割成的段數。

這是實施。

typedef struct { 
    CGMutablePathRef path; 
    int quality; 
} InterpolationInfo; 

static inline float cubeInterp(float t, float p0, float p1, float p2, float p3) { 
    return powf(1-t, 3)*p0 + 3*powf(1-t, 2)*t*p1 + 3*(1-t)*powf(t, 2)*p2 + powf(t, 3)*p3; 
} 

static void pointsForCubeCurve(CGPoint cp0, CGPoint cp1, CGPoint cp2, CGPoint ep, CGPoint *buffer, int numberPoints) { 
    for (int i = 0; i<numberPoints; i++) { 
     float t = (i+1)/(float)numberPoints; 
     buffer[i] = CGPointMake(cubeInterp(t, cp0.x, cp1.x, cp2.x, ep.x), cubeInterp(t, cp0.y, cp1.y, cp2.y, ep.y)); 
    } 
} 

static inline float quadInterp(float t, float p0, float p1, float p2) { 
    return powf(1-t, 2)*p0 + 2*(1-t)*t*p1 + powf(t, 2)*p2; 
} 

static void pointsForQuadCurve(CGPoint cp0, CGPoint cp, CGPoint ep, CGPoint *buffer, int numberPoints) { 
    for (int i = 0; i<numberPoints; i++) { 
     float t = (i+1)/(float)numberPoints; 
     buffer[i] = CGPointMake(quadInterp(t, cp0.x, cp.x, ep.x), quadInterp(t, cp0.x, cp.x, ep.x)); 
    } 
} 

static void CGPathElementConvertToPolygon(void *info, const CGPathElement *element) { 
    InterpolationInfo *interpInfo = info; 
    switch (element->type) { 
     case kCGPathElementMoveToPoint: 
      CGPathMoveToPoint(interpInfo->path, NULL, element->points[0].x, element->points[0].y); 
      break; 
     case kCGPathElementAddLineToPoint: 
      CGPathAddLineToPoint(interpInfo->path, NULL, element->points[0].x, element->points[0].y); 
      break; 
     case kCGPathElementAddQuadCurveToPoint: { 
      int nr = interpInfo->quality; 
      CGPoint buffer[nr]; 
      pointsForQuadCurve(CGPathGetCurrentPoint(interpInfo->path), element->points[0], element->points[1], buffer, nr); 
      for (int i = 0; i<nr; i++) { 
       CGPathAddLineToPoint(interpInfo->path, NULL, buffer[i].x, buffer[i].y); 
      } 
      break; 
     } 
     case kCGPathElementAddCurveToPoint: { 
      int nr = interpInfo->quality; 
      CGPoint buffer[nr]; 
      pointsForCubeCurve(CGPathGetCurrentPoint(interpInfo->path), element->points[0], element->points[1], element->points[2], buffer, nr); 
      for (int i = 0; i<nr; i++) { 
       CGPathAddLineToPoint(interpInfo->path, NULL, buffer[i].x, buffer[i].y); 
      } 
      break; 
     } 
     case kCGPathElementCloseSubpath: 
      CGPathCloseSubpath(interpInfo->path); 
      break; 
     default: 
      break; 
    } 
} 

static CGPathRef CGPathCreatePolygonPath(CGPathRef path, int quality) { 
    CGMutablePathRef newPath = CGPathCreateMutable(); 
    InterpolationInfo info; 
    info.path = newPath; 
    info.quality = quality; 
    CGPathApply(path, &info, CGPathElementConvertToPolygon); 
    return newPath; 
} 

static BOOL CGPathContainsPointInterpolated(CGPathRef path, const CGAffineTransform *m, CGPoint point, bool eoFill, int quality) { 
    CGPathRef polygon = CGPathCreatePolygonPath(path, quality); 
    BOOL returnValue = CGPathContainsPoint(polygon, m, point, eoFill); 
    CGPathRelease(polygon); 
    return returnValue; 
}