Find Convex hull of given points using Gift wrapping algorithm

Find Convex hull of given points using Gift wrapping algorithm

This is implementation of Grift wrapping algorithm for finding convex hull.

  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 findConvexHull(final List vertices)
    {
        if (vertices == null)
            return Collections.emptyList();

        if (vertices.size() < 3)
            return vertices;

        final List points = new ArrayList(vertices);
        final List hull = new ArrayList();
        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);
    }