java

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<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);
    }

3 thoughts on “Find Convex hull of given points using Gift wrapping algorithm

Leave a Reply

Your email address will not be published. Required fields are marked *

* Copy This Password *

* Type Or Paste Password Here *