///shape_to_triangles(shape)
//
//  Returns a list of triangles created from a given 2D polygon.
//
//      polygon     ds_list of an ordered series of coordinate
//                  pairs defining the shape of a polygon
//
//  The polygon vertices are given and returned in traditional
//  counter-clockwise order. Polygons are closed figures with edges
//  spanning consecutive vertices and from the last vertex to the
//  first. Polygons must be simple, which means they cannot have
//  edges that cross one another. The number of triangles created
//  is (n-2), where n is the number of vertices in the polygon.
//
//  eg. in:  square polygon = { 100,100,  100,200,  200,200,  200,100 }
//
//      out: two triangles = { 100,100,  100,200,  200,100,
//                             100,200,  200,200,  200,100 }
//
//  Depends on lines_intersect() and point_in_triangle().
//
/// GMLscripts.com/license
{
    var polygon, polygonSize, triangles, points, polyX, polyY, good;
    var i, j, n, p, A, B, C, x0, y0, x1, y1, x2, y2, x3, y3, x4, y4,
    p0,p1,p2,p3,p4;
    polygon = argument0;
    polygonSize = ds_list_size(polygon);
    triangles = ds_list_create();
    points = ds_list_create();
    polyP = ds_list_create();

    i = 0;
    repeat (polygonSize)
    {
        ds_list_add(polyP, ds_list_find_value(polygon, i));
        i += 1;
    }

    // 1. For (n - 3) vertices
    n = polygonSize;
    for (n = polygonSize; n > 3; n -= 1)
    {
        //  a. Select first point (random)
        ds_list_clear(points);
        for (p = 0; p < n; p += 1) ds_list_add(points, p);
        repeat (p)
        {
            i = floor(random(ds_list_size(points)));
            A = ds_list_find_value(points, i);
            ds_list_delete(points, i);

            //  b. Pick the next two points
            B = (A + 1) mod n;
            C = (A + 2) mod n;

            //  c. Make a triangle with the selected points
            p0 = ds_list_find_value(polyP, A);
            p1 = ds_list_find_value(polyP, B);
            p2 = ds_list_find_value(polyP, C);

            x0 = point_x(p0); y0 = point_y(p0);
            x1 = point_x(p1); y1 = point_y(p1);
            x2 = point_x(p2); y2 = point_y(p2);

            //  d. If triangle is counter-clockwise...
            if ((x1 - x0) * (y2 - y0) + (y0 - y1) * (x2 - x0) < 0)
            {
                good = true;
                //  ...and if triangle has no vertices within it...
                for (i = 0; i < n; i += 1)
                {
                    if ((i != A) && (i != B) && (i != C))
                    {
                        p3 = ds_list_find_value(polyP,i);
                        x3 = point_x(p3);
                        y3 = point_y(p3);
                        if (point_in_triangle(x3, y3, x0, y0, x1, y1, x2, y2))
                        {
                            good = false;
                            break;
                        }
                        //  ...and if the new edge has no other edges crossing it...
                        j = (i + 1) mod n;
                        if ((j != A) && (j != B) && (j != C))
                        {
                            p4 = ds_list_find_value(polyP,j);
                            x4 = point_x(p4);
                            y4 = point_y(p4);

                            if (lines_intersect(x0, y0, x2, y2, x3, y3, x4, y4, true) != 0)
                            {
                                good = false;
                                break;
                            }
                        }
                    }
                }

                //  e.  ...then add the triangle to list and remove the unshared vertex
                if (good)
                {
                    ds_list_add(triangles, p0);
                    ds_list_add(triangles, p1);
                    ds_list_add(triangles, p2);
                    ds_list_delete(polyP, B);
                    break;
                }
            }
        }
    }

    //  2. There are only three vertices left, so add the final triangle to the list
    ds_list_add(triangles, ds_list_find_value(polyP, 0));
    ds_list_add(triangles, ds_list_find_value(polyP, 1));
    ds_list_add(triangles, ds_list_find_value(polyP, 2));

    //  3. Clean up
    ds_list_destroy(polyP);
    ds_list_destroy(points);

    return triangles;
}