不规则多边形三角切割法 OC版

openGL ES 项目中需要绘制不规则的多边形，但openGL ES只支持三角形，三角带，三角扇。但后台给的数据只有顶点坐标没有顶点索引，只能根据顶点坐标把多边形切割成三角形：

耳切法切割多边形的几个主要方法：

1.根据顶点坐标计算多边形带方向面积，主要是为了判断顶点时针方向，正时针面积<0，逆时针>0

+ (float)Area:(NSArray<NSValue *> *)contour {

    int n = (int)contour.count;
    
    float A = 0.0f;
    
    for(int p = n - 1, q = 0 ; q < n; p = q++) {
        
        CGPoint pPoint = [contour[p] CGPointValue];
        CGPoint qPoint = [contour[q] CGPointValue];
        
        A += (pPoint.x * qPoint.y - qPoint.x * pPoint.y);
    }
    return A * 0.5f;
}

2.判断一个点是否在一个三角形（三个点）之中

+ (BOOL)InsideTriangle:(float)Ax :(float)Ay :(float)Bx :(float)By :(float)Cx :(float)Cy :(float)Px :(float)Py {

    float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
    float cCROSSap, bCROSScp, aCROSSbp;
    
    ax = Cx - Bx;  ay = Cy - By;
    bx = Ax - Cx;  by = Ay - Cy;
    cx = Bx - Ax;  cy = By - Ay;
    apx= Px - Ax;  apy= Py - Ay;
    bpx= Px - Bx;  bpy= Py - By;
    cpx= Px - Cx;  cpy= Py - Cy;
    
    aCROSSbp = ax*bpy - ay*bpx;
    cCROSSap = cx*apy - cy*apx;
    bCROSScp = bx*cpy - by*cpx;
    
    BOOL result = (aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f);
    return result;
}

3. 是否符合切割条件

static const float EPSILON = 0.0000000001f;
+ (BOOL)Snip:(NSArray<NSValue *> *)contour :(NSMutableArray *)V :(int)u :(int)v :(int)w :(int)n
{
    float Ax, Ay, Bx, By, Cx, Cy, Px, Py;

    int a = [V[u] intValue];
    CGPoint aPoint = [contour[a] CGPointValue];
    Ax = aPoint.x;
    Ay = aPoint.y;

    int b = [V[v] intValue];
    CGPoint bPoint = [contour[b] CGPointValue];
    Bx = bPoint.x;
    By = bPoint.y;

    int c = [V[w] intValue];
    CGPoint cPoint = [contour[c] CGPointValue];
    Cx = cPoint.x;
    Cy = cPoint.y;

    float temp = ((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax));
    
    if ( EPSILON > temp ) 
        return false;

    for (int p = 0; p < n ; p++) {
        
        if( (p == u) || (p == v) || (p == w) ) continue;
        
        int z = [V[p] intValue];
        CGPoint pPoint = [contour[z] CGPointValue];
        Px = pPoint.x;
        Py = pPoint.y;
        
        if ([self InsideTriangle:Ax :Ay :Bx :By :Cx :Cy :Px :Py]) 
            return false;
    }
    return true;
}

4. 流程

+ (NSMutableArray *)Process:(NSArray<NSValue *> *)contour
{
    NSMutableArray *result = [NSMutableArray array];
    
    NSInteger n = contour.count;
    if ( n < 3 ) return result;
    
    NSMutableArray *V = [NSMutableArray arrayWithCapacity:n];
    
    if ( 0.0f < [self Area:contour] ) {
        for (int v = 0; v < n; v++) {
            NSNumber *num = [NSNumber numberWithInt:v];
            [V insertObject:num atIndex:v];
        }
    } else {
        for(int v = 0; v < n; v++) {
            NSNumber *num = [NSNumber numberWithInt:(int)(n-1)-v];
            [V insertObject:num atIndex:v];
        }
    }
    
    int nv = (int)n;
    
    int count = 2*nv;
    
    for(int v = nv-1; nv > 2; ) {

        if (0 >= (count--)) {
            return result;
        }
        
        int u = v; if (nv <= u) u = 0;    // i - 1
        v = u+1; if (nv <= v) v = 0;      // i
        int w = v+1; if (nv <= w) w = 0;  // i + 1
        
        if ( [self Snip:contour :V :u :v :w :nv]) {
            int a,b,c;
            
            a = [V[u] intValue];
            b = [V[v] intValue];
            c = [V[w] intValue];
            
            // 把切下的三角形放入数组
            [result addObject:contour[a]];
            [result addObject:contour[b]];
            [result addObject:contour[c]];
            
            [V removeObjectAtIndex:v];
            nv--;
            
            count = 2*nv;
        }
    }
    return result;
}

5. 测试

- (void)test
{
    CGPoint a = CGPointMake(2, 2);
    NSValue *value1 = [NSValue valueWithCGPoint:a];
    CGPoint b = CGPointMake(2, -1);
    NSValue *value2 = [NSValue valueWithCGPoint:b];
    CGPoint c = CGPointMake(-1, -1);
    NSValue *value3 = [NSValue valueWithCGPoint:c];
    CGPoint d = CGPointMake(-1, 2);
    NSValue *value4 = [NSValue valueWithCGPoint:d];
    CGPoint e = CGPointMake(0, 2);
    NSValue *value5 = [NSValue valueWithCGPoint:e];
    CGPoint f = CGPointMake(0, 1);
    NSValue *value6 = [NSValue valueWithCGPoint:f];
    CGPoint g = CGPointMake(1, 1);
    NSValue *value7 = [NSValue valueWithCGPoint:g];
    CGPoint h = CGPointMake(1, 2);
    NSValue *value8 = [NSValue valueWithCGPoint:h];

    NSArray *vs = @[value1, value2, value3, value4, value5, value6, value7, value8];

    NSMutableArray *result = [NSMutableArray array];
    
    result = [Triangulate Process:vs];
    
    for (int i = 0; i < result.count/3; i++) {

        CGPoint p1 = [result[i*3+0] CGPointValue];
        CGPoint p2 = [result[i*3+1] CGPointValue];
        CGPoint p3 = [result[i*3+2] CGPointValue];
        
        NSLog(@"Triangle %d => (%0.0f, %0.0f) (%0.0f, %0.0f) (%0.0f, %0.0f)\n", i+1, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
    }
}

6.结果

测试结果.png

参考：
http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml