(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(ListmyPointsList) {
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, ListmyPointsList) {
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 Listgraham(List myPointsList) {
if (myPointsList.size() < 2) {
return myPointsList;
}
final LinkedListp2ds = 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à!
