Convex Hull Algorithm

Convex hull: the smallest polygon that covers all the points in the given set.

Application: Farthest pair problem, shortest Path across the boundary.

Algorithm: Find the point with the lowest y-coordinates p, then iterate through all the points in the order of polar-angle relative to the p. Check if they can form a counter clock wise angle with the previous point, if so include it in the context hull, otherwise discard it. There is a video clip explaining the convex hull algorithm

https://www.youtube.com/watch?v=0HZaRu5IupM

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;
 
 
public class ConvexHull {
    //assume no duplicate points 
    public static void main(String [] args) {
        ArrayList<Point> points = new ArrayList<Point> ();
        points.add(new Point(0, 0));
        points.add(new Point(1, 1));
        points.add(new Point(3, 10));
        points.add(new Point(8, 7));
        points.add(new Point(11, 8));
        points.add(new Point(12, 1));
        ArrayList<Point> result = new ArrayList<Point>();
        //check if there are more than three points in the array
        if (points.size() < 3) {
            System.out.println("Too few points");
            return;
        }
         
        //find the point with the lowest y
        int oIndex = 0;
        for (int i = 1; i < points.size(); i++) {
            if (points.get(i).y < points.get(oIndex).y)
                oIndex = i;
        }
        //remove the origin points and put it into the stack
        final Point origin = points.get(oIndex);
        points.remove(oIndex);
         
        //stack that we use to iterate through the 
        Stack<Point> hullStack = new Stack<Point>();
        hullStack.push(origin); //put origin point in stack
        //sort the points according to their polarity relative to origin
        Collections.sort(points, new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                float polar1 = getPolar(origin, p1);
                float polar2 = getPolar(origin, p2);
                if (polar1 > polar2)
                    return -1;
                else if (polar1 < polar2)
                    return 1;
                return 0;
            }       
        });
        //add origin to as the last element
        points.add(origin);
        for (Point p : points) {
            Point pre = hullStack.pop();
            while(!hullStack.isEmpty() && !isLeftTurn(hullStack.peek(), pre, p)) {
                pre = hullStack.pop();//discard the pre and take new top of the stack as pre
            }
            hullStack.push(pre);
            hullStack.push(p);
        }
        //remove the duplicate origin
        hullStack.pop();
        while(!hullStack.isEmpty()) {
            result.add(hullStack.pop());
        }
    }
     
    private static float getPolar(Point start, Point end) {
        //get the cosin between end and start
        float r = ((end.x - start.x)*(end.x - start.x) + (end.y - start.y)*(end.y - start.y));
        return (float) ((end.x - start.x)/Math.pow(r, 0.5)); 
    }
     
    private static boolean isLeftTurn(Point a, Point b, Point c) {
        if ((c.y - a.y)/(c.x - a.x) > (b.y - a.y)/(b.x - a.x))
            return true;
        return false;
    }
}

  

The above program shows an way get a convex hull from a set of points.
The running time is dominated by the sorting so it is nlogn.

Two things need to pay attention:
1. the original point is the one with the lowest y coordinate. So all the other point was above it. We want the points to be sorted according to the polar angle relative to the original point, in the order of counterclockwise. So we should use cosin which on the uppper part of coordinate system, decrease in the order of counterclock direction.

2. To find out whether we make a left (counter clock wise) turn in a three point a->b->c, there is a simple way. We should check if (c.y – a.y)*(b.x – a.x) – (b.y – a.y)*(c.x – a.x). If it is equals to 0, then a, b and c are on the same line. if positive, it is making a left turn, otherwise it is making a right turn.

 

From:

https://hellosmallworld123.wordpress.com/2014/08/01/convex-hull-algorithm/