Convex Hull

Here is an easy way to compute a convex hull, being given a set of points in Java.
(Check out Graham Scan)

Let's say that we have the set of points defined as follows:

List _pointsList = new LinkedList();

A P2D being:

public class P2D {
  private Point2D point2d = new Point2D.Double();
  private String id = null;
    
  public P2D(String id, double x, double y) {
    this.id = id;
    this.point2d.setLocation(x, y);
  }
...

The first step is to find the pivot:

private P2D findPivot(List myPointsList) {
  P2D pivot = myPointsList.get(0);
  
  for(final P2D p2d : myPointsList) {
    if (p2d.getY() < pivot.getY()) {
      pivot = p2d;
    }
  }
  
  return pivot;
}

Then we do the sort:

private void sort(P2D pivot, List myPointsList) {
  final GrahamComparator grahamComparator = new GrahamComparator(pivot);
  Collections.sort(myPointsList, grahamComparator);
}

The comparator being defined as:

public class GrahamComparator implements Comparator {
  private final P2D pivot;
    
  public GrahamComparator(P2D pivot) {
    this.pivot = pivot;
  }
    
  public int compare(P2D p2d1, P2D p2d2) {
    Double tan1 = (p2d1.getX() - pivot.getX()) / (p2d1.getY() - pivot.getY());
    Double tan2 = (p2d2.getX() - pivot.getX()) / (p2d2.getY() - pivot.getY());
    return tan2.compareTo(tan1);
  }
}

And finally, the main algorithm that returns a list of points, the convex hull:

private List graham(List myPointsList) {
  if (myPointsList.size() < 2) {
    return myPointsList;
  }
        
  final LinkedList p2ds = new LinkedList();
        
  p2ds.add(0, myPointsList.get(0)); // Pivot
  p2ds.add(1, myPointsList.get(1)); // Second sorted element
        
  for(int i=2; i < myPointsList.size(); i++) {
    while(p2ds.size() >= 2 && crossProduct(p2ds.get(p2ds.size()-1), p2ds.get(p2ds.size()-2), myPointsList.get(i)) > 0) {
      p2ds.removeLast();
    }
    p2ds.addLast(myPointsList.get(i));
  }
  return p2ds;
}

with the cross product defined as:

private double crossProduct(P2D p1, P2D p2, P2D p3) {
  final double cp = (p2.getX() - p1.getX())*(p3.getY() - p1.getY()) - (p3.getX() - p1.getX())*(p2.getY() - p1.getY());
  return cp;
}

Et voilà!