我有一个代码可以让用户绘制一个形状，为此我使用了 UIBezierPath。但我需要查看形状是否与自身交叉，例如:http://upload.wikimedia.org/wikipedia/commons/0/0f/Complex_polygon.svg 那么它不是一个有效的形状。 我怎样才能找到它？

编辑: 我还没有解决这个问题。我将路径中各行之间的所有点保存在一个数组中。然后我遍历数组并尝试查找是否有任何线相交。但是它不起作用，有时它说有一个交叉点而实际上没有。

我认为问题出在这个方法的某个地方。

-(BOOL)pathIntersects:(double *)x:(double *)y {
int count = pathPoints.count;
CGPoint p1, p2, p3, p4;
for (int a=0; a<count; a++) {

    //Line 1
    if (a+1<count) {
        p1 = [[pathPoints objectAtIndex:a] CGPointValue];
        p2 = [[pathPoints objectAtIndex:a+1] CGPointValue];
    }else{
        return NO;
    }

    for (int b=0; b<count; b++) {

        //Line 2
        if (b+1<count) {
            p3 = [[pathPoints objectAtIndex:b] CGPointValue];
            p4 = [[pathPoints objectAtIndex:b+1] CGPointValue];
        }else{
            return NO;
        }


        if (!CGPointEqualToPoint(p1, p3) && !CGPointEqualToPoint(p2, p3) && !CGPointEqualToPoint(p4, p1) && !CGPointEqualToPoint(p4, p2)
            && !CGPointEqualToPoint(p1, p2) && !CGPointEqualToPoint(p3, p4)) {

            if (LineIntersect(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y, x, y)) { 
                return YES;
            }

        }

    }
}
return NO;
}

这是我发现的用于查看两条线是否相交的代码，它是用 C 编写的，但我应该可以工作。

int LineIntersect(
              double x1, double y1,
              double x2, double y2,
              double x3, double y3,
              double x4, double y4,
              double *x, double *y)
{
double mua,mub;
double denom,numera,numerb;

denom  = (y4-y3) * (x2-x1) - (x4-x3) * (y2-y1);
numera = (x4-x3) * (y1-y3) - (y4-y3) * (x1-x3);
numerb = (x2-x1) * (y1-y3) - (y2-y1) * (x1-x3);

/* Are the line coincident? */
if (ABS(numera) < 0.00001 && ABS(numerb) < 0.00001 && ABS(denom) < 0.00001) {
    *x = (x1 + x2) / 2;
    *y = (y1 + y2) / 2;
    return(TRUE);
}

/* Are the line parallel */
if (ABS(denom) < 0.00001) {
    *x = 0;
    *y = 0;
    return(FALSE);
}

/* Is the intersection along the the segments */
mua = numera / denom;
mub = numerb / denom;
if (mua < 0 || mua > 1 || mub < 0 || mub > 1) {
    *x = 0;
    *y = 0;
    return(FALSE);
}
*x = x1 + mua * (x2 - x1);
*y = y1 + mua * (y2 - y1);
return(TRUE);
}

最佳答案

这取决于用户绘制的多边形的复杂程度和路径中的点数。理想情况下，形状中的所有顶点都会有一个点，仅此而已。从 UIBezierPath 获取 CGPath 并使用 GCPathApply 将元素交给一个函数，该函数将每个点添加到一个数组。使用两个 for 循环遍历数组，一个嵌套在另一个循环中，使用标准的线对线相交测试检查每条线段之后的每条线段。一旦找到交叉点，就从循环中断开。或者，如果这是一个方便的方法，则返回一个 BOOL。这是最简单的方法。

编辑:这里有一个直线相交函数的例子，它返回一个 BOOL 值，告诉您两条线段是否交叉。传入创建第一段的两个点，然后传入创建第二段的两个点。它是根据我在网上快速找到的一段源代码仓促修改的，但它确实有效。

CGPoint lineSegmentsIntersect(CGPoint L1P1, CGPoint L1P2, CGPoint L2P1, CGPoint L2P2) 
{ 
    float x1 = L1P1.x, x2 = L1P2.x, x3 = L2P1.x, x4 = L2P2.x;
    float y1 = L1P1.y, y2 = L1P2.y, y3 = L2P1.y, y4 = L2P2.y;

    float bx = x2 - x1; 
    float by = y2 - y1; 
    float dx = x4 - x3; 
    float dy = y4 - y3;

    float b_dot_d_perp = bx * dy - by * dx;

    if(b_dot_d_perp == 0) {
        return NO;
    }

    float cx = x3 - x1;
    float cy = y3 - y1;
    float t = (cx * dy - cy * dx) / b_dot_d_perp;

    if(t < 0 || t > 1) {
        return NO;
    }

    float u = (cx * by - cy * bx) / b_dot_d_perp;

    if(u < 0 || u > 1) { 
        return NO;
    }

    return YES;
}

你可以像这样使用它。

if (lineSegmentsIntersect(lineOnePointOne,lineOnePointTwo,lineTwoPointOne,lineTwoPointTwo)){
     //segments intersect
} else {
     //segments did not intersect
}

由您来创建双循环来相互检查正确的段。

关于objective-c - 贝塞尔路径看是否交叉，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13394422/