判断多边形是否自相交

多边形相交

//***************点积判点是否在线段上***************
+ (int)dblcmp:(double)a b:(double)b {
    if (fabs(a - b) <= 1E-6) return 0;
    if (a > b) return 1;
    else return -1;
}
//点积
+ (double)dot:(double)x1 y1:(double)y1 x2:(double)x2 y2:(double)y2 {
    return x1 * x2 + y1 * y2;
}
//求a点是不是在线段bc上，>0不在，=0与端点重合，<0在。
+ (int)point_on_line:(MAMapPoint)a b:(MAMapPoint)b c:(MAMapPoint)c {
    return [self dblcmp:[self dot:b.x - a.x y1:b.y - a.y x2:c.x - a.x y2:c.y - a.y] b:0];
}
//**************************************************
+ (double)cross:(double)x1 y1:(double)y1 x2:(double)x2 y2:(double)y2 {
    return x1 * y2 - x2 * y1;
}
//ab与ac的叉积
+ (double)ab_cross_ac:(MAMapPoint)a b:(MAMapPoint)b c:(MAMapPoint)c {
    return [self cross:b.x - a.x y1:b.y - a.y x2:c.x - a.x y2:c.y - a.y];
}
//求ab是否与cd相交，交点为p。1规范相交，0交点是一线段的端点，-1不相交。
+ (int)ab_cross_cd:(MAMapPoint)a b:(MAMapPoint)b c:(MAMapPoint)c d:(MAMapPoint)d {
    double s1,s2,s3,s4;
    int d1,d2,d3,d4;
    MAMapPoint p = MAMapPointMake(0, 0);
    d1 = [self dblcmp:s1 = [self ab_cross_ac:a b:b c:c] b:0];
    d2 = [self dblcmp:s2 = [self ab_cross_ac:a b:b c:d] b:0];
    d3 = [self dblcmp:s3 = [self ab_cross_ac:c b:d c:a] b:0];
    d4 = [self dblcmp:s4 = [self ab_cross_ac:c b:d c:b] b:0];
    
    //如果规范相交则求交点
    if ((d1^d2) == -2 && (d3^d4) == -2) {
        p.x = (float) ((c.x * s2-d.x * s1) / (s2 - s1));
        p.y = (float) ((c.y * s2-d.y * s1) / (s2 - s1));
        NSLog(@"规范相交-Point:(x=%lf,y=%lf)", p.x, p.y);
        return 1;
    }
    
    //如果不规范相交
    if (d1 == 0 && [self point_on_line:c b:a c:b] <= 0) {
        p = c;
        return 0;
    }
    if (d2 == 0 && [self point_on_line:d b:a c:b] <= 0) {
        p = d;
        return 0;
    }
    if (d3 == 0 && [self point_on_line:a b:c c:d] <= 0) {
        p = a;
        return 0;
    }
    if (d4 == 0 && [self point_on_line:b b:c c:d] <= 0) {
        p = b;
        return 0;
    }
    //如果不相交
    return -1;
}

使用方法如下：

//points为多边形的所有点——最后一个点和第一个点不重合
+ (BOOL)checkCross:(MAMapPoint *)points count:(NSInteger)count {
    BOOL isCorss = NO;
    for (int i = 0; i < count - 1; i++) {
        for (int j = i + 1; j < count; j++) {
            MAMapPoint point3;
            if (j == count - 1) {
                point3 = points[0];
            }else {
                point3 = points[j + 1];
            }
            
            MAMapPoint point = points[i];
            MAMapPoint point1 = points[i+1];
            MAMapPoint point2 = points[j];
            
            if ([self ab_cross_cd:point b:point1 c:point2 d:point3] == 1) {
                return true;
            }
        }
    }
    
    return isCorss;
}

转载时请注明“来自简书-EvenZhu”