typedef struct
    {
        float x, y;
    } Point2D;
    
    typedef struct
    {
        Point2D p1, p2, p3;
    } Triangle2D;
    
    Triangle2D* Terrain::Process( int nb_points, Point2D *points, int& nb_triangles )
    {
        /* allocate and initialize list of Vertices in polygon */
        Triangle2D *triangles = new Triangle2D[nb_points-2];
        nb_triangles = 0;
    
        int n = nb_points;
        if ( n < 3 ) return false;
    
        int *V = new int[n];
    
        /* we want a counter-clockwise polygon in V */
    
        if ( 0.0f < Area(nb_points, points) )
            for (int v=0; v<n; v++) V[v] = v;
        else
            for(int v=0; v<n; v++) V[v] = (n-1)-v;
    
        int nv = n;
    
        /*  remove nv-2 Vertices, creating 1 triangle every time */
        int count = 2*nv;   /* error detection */
    
        for(int m=0, v=nv-1; nv>2; )
        {
    
            /* if we loop, it is probably a non-simple polygon */
            if (0 >= (count--))
            {
                //** Triangulate: ERROR - probable bad polygon!
                // delete[] triangles;
                printf( "Degenerate polygon\n" );
                return triangles;
            }
    
            /* three consecutive vertices in current polygon, <u,v,w> */
            int u = v  ; if (nv <= u) u = 0;     /* previous */
            v = u+1; if (nv <= v) v = 0;     /* new v    */
            int w = v+1; if (nv <= w) w = 0;     /* next     */
    
            if ( Snip(nb_points, points,u,v,w,nv,V) )
            {
                int a,b,c,s,t;
    
                /* true names of the vertices */
                a = V[u]; b = V[v]; c = V[w];
    
                /* output Triangle */
                /*   result.push_back( points[a] );
          result.push_back( points[b] );
          result.push_back( points[c] );*/
    
                triangles[nb_triangles].p1 = points[a];
                triangles[nb_triangles].p2 = points[b];
                triangles[nb_triangles].p3 = points[c];
                nb_triangles++;
    
                m++;
    
                /* remove v from remaining polygon */
                for(s=v,t=v+1;t<nv;s++,t++) V[s] = V[t]; nv--;
    
                /* resest error detection counter */
                count = 2*nv;
            }
        }
    
        delete V;
    
        return triangles;
    }
    
    float Terrain::Area( int nb_points, Point2D *points )
    {
    
        int n = nb_points;
    
        float A=0.0f;
    
        for(int p=n-1,q=0; q<n; p=q++)
        {
            A+= points[p].x*points[q].y - points[q].x*points[p].y;
        }
        return A*0.5f;
    }
    
    
    bool Terrain::Snip( int nb_points, Point2D *points,int u,int v,int w,int n,int *V )
    {
        int p;
        float Ax, Ay, Bx, By, Cx, Cy, Px, Py;
    
        Ax = points[V[u]].x;
        Ay = points[V[u]].y;
    
        Bx = points[V[v]].x;
        By = points[V[v]].y;
    
        Cx = points[V[w]].x;
        Cy = points[V[w]].y;
    
        if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return false;
    
        for (p=0;p<n;p++)
        {
            if( (p == u) || (p == v) || (p == w) ) continue;
            Px = points[V[p]].x;
            Py = points[V[p]].y;
            if (InsideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)) return false;
        }
    
        return true;
    }
    
    bool Terrain::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;
    
        return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
    }

976130.4 6449595.49999999

976127.2 6449598.09999999

976124.7 6449601.79999999

976122.4 6449605.79999999

976120.3 6449610.09999999

976117.2 6449615.39999999

976115.7 6449619.29999999

976114.9 6449623.59999999

976115.7 6449627.49999999

976119.4 6449630.69999999

976121.7 6449634.89999999

976120.6 6449639.49999999