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

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

GregThanks, code should reflect your change.

SRMWhat exactly does getExtremePoint() do?