Listing 2: The triangulation algorithm

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

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


void
triangulate (const Polygon & input_P, 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, 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);
}
//End of File