Listing 3: Finding the convex hull of an arbitrary set of points

#include "Polygon.h"
#include "Point.h"
#include "Triangle.h"
#include <list>

using namespace std;


Polygon convex_hull_set_points (const list<Point> & points)
{
    Polygon result; 
    list<Point>::const_iterator i;
    Point p_min_y = *(points.begin());

    for (i = points.begin(); i != points.end(); i++)
    {
        if ((*i).get_y() < p_min_y.get_y())
        {
            p_min_y = *i;
        }
    }

        // Now search always right-most point with respect 
        // to the last found to be on the convex hull

    result.push_back (p_min_y);

    Point p = p_min_y;
    Point new_p;

    do
    {
        i = points.begin ();
        if (p != *i)
        {
            new_p = *i;
        }
        else
        {
            new_p = *++i;
        }

        for (i = points.begin(); i != points.end(); i++)
        {
            if (turn (p, new_p, *i) == right_turn)
            {
                new_p = *i;
            }
        }

        if (new_p != p_min_y)       // If not the first one
        {
            result.push_back (new_p);
        }
        p = new_p;                  // Advance
    }
    while (new_p != p_min_y);

    return result;
}
//End of File