贝塞尔path看它是否穿越

我有一个让用户绘制形状的代码，我使用UIBezierPath。 但是我需要看看形状是否自相交叉，例如像这样： http : //upload.wikimedia.org/wikipedia/commons/0/0f/Complex_polygon.svg然后它不是一个有效的形状。 我怎样才能find这个？

编辑：我还没有解决这个。 我保存数组中path之间的所有点。 然后我遍历数组，并尝试查找是否有任何线相交。 但是它不起作用，有时它说不存在交叉点。

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

-(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); } 

Answer 1

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

编辑：这是一个线条交集函数的例子，它返回一个布尔告诉你两个段是否交叉。 通过创build第一个分段的两个点，然后是构成第二个分段的两个点。 从我在网上find的一段源代码中匆匆修改过，但是它起作用了。

 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 } 

您可以创build双循环来检查相互正确的段。