/*
**  Usage:
**      triangles = polygon_to_triangles(polygon);
**
**  Description:
**      Takes a list of points defining the boundary of a polygon
**      and returns a list of triangles in the same shape.
**
**  Arguments:
**      polygon      ds_list containing XY coordinate pairs defining
**                   the shape of a polygon
**
**  Returns:
**      triangles    ds_list containing triplets of XY coordinate pairs
**
**  Dependencies:
**      is_clockwise()
**      lines_intersect()
**      point_in_triangle()
**
**  Notes:
**      The polygon points are given and returned in traditional
**      counter-clockwise order. Polygons are closed figures, the
**      first point in the polygon will also be considered the last
**      point in the polygon. Polygons must be simple, which means
**      they can not have edges that cross each other. The number
**      of triangles created is (n-2) where n is the number of
**      points in the polygon.
**
**  Example:
**      in:  polygon = [ 100,100,  100,200,  200,200,  200,100 ]
**           (a square polygon: four coordinate pairs)
**
**      out: triangles = [ 100,100,  100,200,  200,100,   (1st triplet)
**                         100,200,  200,200,  200,100 ]  (2nd triplet)
**           (two triangles: two triplet sets of coordinate pairs)
**
**  copyright (c) 2006, John Leffingwell
**  www.planetxot.com
*/
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;
polygon = argument[0];
polygonSize = ds_list_size(polygon) div 2;
triangles = ds_list_create();
points = ds_list_create();
polyX = ds_list_create();
polyY = ds_list_create();
i = 0;
repeat (polygonSize) {
    ds_list_add(polyX, ds_list_find_value(polygon, i));
    ds_list_add(polyY, ds_list_find_value(polygon, i+1));
    i += 2;
}
// 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
        x0 = ds_list_find_value(polyX, A);
        y0 = ds_list_find_value(polyY, A);
        x1 = ds_list_find_value(polyX, B);
        y1 = ds_list_find_value(polyY, B);
        x2 = ds_list_find_value(polyX, C);
        y2 = ds_list_find_value(polyY, C);
        //  d. If triangle is counter-clockwise...
        if (not is_clockwise(x0, y0, x1, y1, x2, y2)) {
            good = true;
            //  ...and if triangle has no vertices within it...
            for (i = 0; i < n; i += 1) {
                if ((i != A) && (i != B) && (i != C)) {
                    x3 = ds_list_find_value(polyX, i);
                    y3 = ds_list_find_value(polyY, i);
                    if (point_in_triangle(x0, y0, x1, y1, x2, y2, x3, y3)) { 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)) {
                        x4 = ds_list_find_value(polyX, j);
                        y4 = ds_list_find_value(polyY, j);
                        if (lines_intersect(x0, y0, x2, y2, x3, y3, x4, y4)) { good = false; break; }
                    }
                }
            }
            //  e.  ...then add the triangle to list and remove the shared outside edge point
            if (good) {
                ds_list_add(triangles, x0);
                ds_list_add(triangles, y0);
                ds_list_add(triangles, x1);
                ds_list_add(triangles, y1);
                ds_list_add(triangles, x2);
                ds_list_add(triangles, y2);
                ds_list_delete(polyX, B);
                ds_list_delete(polyY, 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(polyX, 0));
ds_list_add(triangles, ds_list_find_value(polyY, 0));
ds_list_add(triangles, ds_list_find_value(polyX, 1));
ds_list_add(triangles, ds_list_find_value(polyY, 1));
ds_list_add(triangles, ds_list_find_value(polyX, 2));
ds_list_add(triangles, ds_list_find_value(polyY, 2));
//  3. Clean up
ds_list_destroy(polyX);
ds_list_destroy(polyY);
ds_list_destroy(points);
return triangles;