# 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”

1. MDK says:

Small typo in dist method – there should be dy = (q.y – p.y) instead of dy = (q.y – p.x).

2. Thanks, code should reflect your change.

3. SRM says:

What exactly does getExtremePoint() do?