// **********************************************************
//   File: triangulation.cpp
//   Description: Triangulation algorithm.  The function 
//                triangulate() is called by client code,
//                and the function recursive_triangulation()
//                is used by triangulate() to execute the 
//                recursive algorithm
//
//   Author: Carlos Moreno
// **********************************************************

#include "Polygon.h"
#include "Point.h"
#include "Triangle.h"

static void recursive_triangulation (Polygon &, std::list<Triangle> &);


void triangulate (const Polygon & input_P, std::list<Triangle> & output)
{
    Polygon P = input_P;    // Make a working copy of parameter

    output.clear ();        // Only the first time.  Recursive 
                            // calls should not clear the list 
                            // of triangles
    
    recursive_triangulation (P, output);
}


static void recursive_triangulation (Polygon & P, std::list<Triangle> & output)
{
    Polygon::iterator current = P.begin();

    
    if ((current+3) == current)   // If polygon contains 3 vertices
    {
        output.push_back (Triangle (*current, *(current+1), *(current+2)));
        return;
    }

    bool done = false;
    do
    {
        Triangle t (*(current-1), *current, *(current+1));
        if (t.orientation() == counter_clockwise)   // if convex vertex
        {
            bool empty_triangle = true;
            Polygon::const_iterator i = current+2, 
                                    farthest_point = current-1;
            do
            {

                if (t.contains (*i))
                {
                    empty_triangle = false;
                    if (Triangle(*(current+1), *(current-1), *i).area() > 
                        Triangle(*(current+1), *(current-1), *farthest_point).area())
                    {
                        farthest_point = i;
                    }
                }
                i++;
            }
            while (i != current-1);

            if (empty_triangle)     // send it to the triangulation
            {
                output.push_back (t);
                current = P.remove (current);
                current--;
                if ((current+3) == current)     // If P became a triangle, done
                {
                    output.push_back (Triangle (*current, *(current+1), *(current+2)));
                    return;
                }
            }
            else    // t not empty ==> split the polygon and triangulate both halves
            {
                Polygon first_half, second_half;

                for (i = current; i != farthest_point; i++)
                {
                    first_half.push_back (*i);
                }
                first_half.push_back (*farthest_point);

                recursive_triangulation (first_half, output);

                for (i = farthest_point; i != current; i++)
                {
                    second_half.push_back (*i);
                }
                second_half.push_back (*current);

                recursive_triangulation (second_half, output);

                return;
            }
        }
        current++;
    }
    while (true);
}
