贝塞尔曲线路径是否穿过 [英] Bezier path see if it crosses

问题描述

我有一个允许用户绘制形状的代码，为此我正在使用UIBezierPath.但是我需要查看形状是否交叉，例如: http ://upload.wikimedia.org/wikipedia/commons/0/0f/Complex_polygon.svg 那就不是有效的形状. 我怎么找到这个?

I have a code that lets the user draw a shape, I'm using UIBezierPath for this. But I need to see if the shape crosses itself, for example like this: http://upload.wikimedia.org/wikipedia/commons/0/0f/Complex_polygon.svg Then it's not a a valid shape. How can I find this?

我仍然没有解决这个问题.我将所有点之间的点保存在数组中的路径中.然后，我遍历数组并尝试查找是否有任何线相交.但这是行不通的，有时会说没有时有一个交叉点.

I still haven't solved this. I save all the points between the lines in the path in a array. And then I loop through the array and try to find if any lines intersects. But it does not work, sometimes it says that there is an intersection when it isn't.

我认为问题出在这种方法中.

I think that the problem is somewhere in this method.

-(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语言中，但我应该工作.

This is the code I found to see if two lines intersects, It's in C but I should work.

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循环遍历该数组，一个for循环嵌套在另一个for循环中，该循环使用标准的line-line相交测试对照每个line segment对其进行检查.一旦找到交叉点，就从环路中中断.或者，如果这是一种便捷方法，则返回BOOL.那是最简单的方法.

It depends on how complex the polygon drawn by the user can be and the number of points in the path. Ideally, there would be a point for all the vertices in the shape and nothing more. Get a CGPath from the UIBezierPath and use GCPathApply to hand the elements to a function, which adds each point to an array. Traverse the array with two for loops, one nested in the other, which checks each line segment against every line segment after it using a standard line-line intersection test. As soon as an intersection has been found, break from the loop. Or, if this were a convenience method, return a BOOL. That's the simplest way.

这是一个线-线相交函数的示例，该函数返回BOOL告诉您两个线段是否交叉.传入创建第一段的两个点，然后传入组成第二段的两个点.我迅速在网上找到了一段源代码，对它进行了快速修改，但是它可以正常工作.

Here's an example of a line-line intersection function which returns a BOOL telling you whether or not two segments cross. Pass in the two points that create the first segment followed by the two points that make the second segment. It was hastily modified from a piece of source code I found online quickly, but it works.

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
}

由您自己决定创建双循环，以针对彼此检查正确的分段.

It's up to you to create the double loop to check the correct segments against one another.

这篇关于贝塞尔曲线路径是否穿过的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！