Find Convex hull of given points using Gift wrapping algorithm

 
  private static final Integer ZERO = new Integer(0);
 
 
/**
     * Find Convex hull of given points
     * 
     * @ref http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
     * @param vertices
     * @return
     */
    private static List<Point> findConvexHull(final List<Point> vertices)
    {
        if (vertices == null)
            return Collections.emptyList();
 
        if (vertices.size() < 3)
            return vertices;
 
        final List<Point> points = new ArrayList<Point>(vertices);
        final List<Point> hull = new ArrayList<Point>();
        Point pointOnHull = getExtremePoint(points, true);
        Point endpoint = null;
        do
        {
            hull.add(pointOnHull);
            endpoint = points.get(0);
 
            for (final Point r : points)
            {
                // Distance is used to find the outermost point -
                final int turn = findTurn(pointOnHull, endpoint, r);
                if (endpoint.equals(pointOnHull) || turn == -1 || turn == 0
                    && dist(pointOnHull, r) > dist(endpoint, pointOnHull))
                {
                    endpoint = r;
                }
            }
            pointOnHull = endpoint;
        } while (!endpoint.equals(hull.get(0))); // we are back at the start
 
        return hull;
    }
 
 
    private static double dist(final Point p, final Point q)
    {
        final double dx = (q.x - p.x);
        final double dy = (q.y - p.y);
        return dx * dx + dy * dy;
    }
 
 
   /**
     * Returns -1, 0, 1 if p,q,r forms a right, straight, or left turn. 
     * 1 = left, -1 = right, 0 = none
     * 
     * @ref http://www-ma2.upc.es/geoc/mat1q1112/OrientationTests.pdf
     * @param p
     * @param q
     * @param r
     * @return 1 = left, -1 = right, 0 = none
     */
    private static int findTurn(final Point p, final Point q, final Point r)
    {
        final int x1 = (q.x - p.x) * (r.y - p.y);
        final int x2 = (r.x - p.x) * (q.y - p.y);
        final int anotherInteger = x1 - x2;
        return ZERO.compareTo(anotherInteger);
    }