Friday 28 September 2007

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à!

No comments:

Blog Archive