2

我有一个代码可以让用户绘制一个形状，我为此使用 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);
}
4

1 回答 1

3

这取决于用户绘制的多边形有多复杂以及路径中的点数。理想情况下，形状中的所有顶点都会有一个点，仅此而已。从 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
}

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

于 2012-11-15T17:51:41.277 回答