http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

geometry.d

struct Point { float x, y; }


Point[] triangulate(const ref Point[] contour)
{
    assert (contour.length > 2);

    Point[] result;
    scope size_t[] V;  // TODO: V.reserve(contour.length)

    // we want a counter-clockwise polygon in V
    if (0.0f < area(contour))
    {
        foreach (i; 0 .. contour.length)
        {
            if (i == 0 || contour[i-1] != contour[i])
                V ~= i;
        }
    }
    else
    {
        foreach (j; 0 .. contour.length)
        {
            size_t i = (contour.length - 1) - j;
            //~ if (i != 0 && contour[i-1] != contour[i])
                V ~= i;
        }
    }

    auto nv = V.length;

    // remove nv-2 Vertices, creating 1 triangle every time
    auto count = 2 * nv;  // error detection

    for (auto m = 0, v = nv - 1; nv > 2; --count)
    {
        if (0 >= count)
        {
            // if we loop, it is probably a non-simple polygon
            throw new Exception("bad polygon");
        }

        // three consecutive vertices in current polygon, <u, v, w>
        auto u = v;
        if (nv <= u)
            u = 0;  // previous
        v = u+1; if (nv <= v) v = 0;  // new v
        auto w = v+1;
        if (nv <= w)
            w = 0;  // next

        if (snip(contour, u, v, w, nv, V))
        {
            // true names of the vertices
            auto a = V[u];
            auto b = V[v];
            auto c = V[w];

            // output Triangle
            result ~= contour[a];
            result ~= contour[b];
            result ~= contour[c];

            m++;

            // remove v from remaining polygon
            for (auto s = v, t = v + 1; t < nv; s++, t++)
                V[s] = V[t];

            nv--;

            // resest error detection counter
            count = 2*nv;
        }
    }

    delete V;
    return result;
}


// compute area of a contour/polygon
float area(const ref Point[] contour)
{
    const n = contour.length;
    float A=0.0f;
    for (auto p = n - 1, q = 0; q < n; p = q++)
    {
        A += contour[p].x * contour[q].y - contour[q].x*contour[p].y;
    }
    return A*0.5f;
}


// decide if point Px/Py is inside triangle defined by
// (Ax, Ay) (Bx, By) (Cx, Cy)
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;

    return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
}


private:

bool snip(const ref Point[] contour, ulong u, ulong v, ulong w, ulong n, ulong[] V)
{
    int p;
    float Ax, Ay, Bx, By, Cx, Cy, Px, Py;

    Ax = contour[V[u]].x;
    Ay = contour[V[u]].y;

    Bx = contour[V[v]].x;
    By = contour[V[v]].y;

    Cx = contour[V[w]].x;
    Cy = contour[V[w]].y;

    if (0.0000000001f > (((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 = contour[V[p]].x;
        Py = contour[V[p]].y;

        if (insideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py))
            return false;
    }

    return true;
}



version (unittest)
void main()
{
    auto poly1 = [Point(0,6), Point(0,0), Point(3,0), Point(4,1),
                Point(6,1), Point(8,0), Point(12,0), Point(13,2),
                Point(8,2), Point(8,4), Point(11,4), Point(11,6),
                Point(6,6), Point(4,3), Point(2,6)];
    auto poly2 = [Point(49,37), Point(74,36), Point(78,38), Point(83,55),
                Point(103,67), Point(107,85), Point(99,89), Point(95,86),
                Point(91,81), Point(85,75), Point(54,46), Point(53,41),
                Point(51,41)];

    triangulate(poly1);
    triangulate(poly2);
}