Convex Hull

From programming_contest
Jump to: navigation, search
 1 /**
 2  * Get the convex of a graph
 3  * default is exclusive, see comments for inclusivity
 4  * @param in input
 5  * @return output
 6  */
 7 public ArrayList<Point> convexHull(ArrayList<Point> in){//default is exclusive, see 2 comments for inclusivity
 8 	LinkedList<Point> out=new LinkedList<Point>();
 9 	Point temp=new Point(0,Integer.MAX_VALUE);
10 	for(Point p:in)if(p.y<temp.y||(p.y==temp.y&&p.x<temp.x))temp=p;
11 	final Point min=new Point(temp);
12 	TreeSet<Point> pq=new TreeSet<Point>(new Comparator<Point>(){
13 		public int compare(Point p0, Point p1) {
14 			double temp=Math.atan2(p0.y-min.y,p0.x-min.x)-Math.atan2(p1.y-min.y,p1.x-min.x);
15 			if(temp<0||(temp==0&&min.distance(p0)<min.distance(p1)))return -1;
16 			return 1;
17 		}
18 	});
19 	out.add(min);
20 	for(Point p:in)if(!p.equals(min))pq.add(p);
21 	while(!pq.isEmpty()){
22 		if(out.size()<2)out.add(pq.pollFirst());
23 		if(pq.isEmpty())break;//this line only necessary for degenerate case
24 		Point m=out.getLast(),n=out.get(out.size()-2),o=pq.first();
25 		if((m.x-n.x)*(o.y-m.y)-(o.x-m.x)*(m.y-n.y)>0)out.add(pq.pollFirst());//take left hand turn only, change to >= for inclusivity
26 		else out.remove(out.size()-1);
27 	}
28 /*		ArrayList<Point> tail=new ArrayList<Point>();//this block is only needed for inclusivity
29 	for(Point p:in)if(!p.equals(min)&&(p.x-min.x)*(out.getLast().y-p.y)-(out.getLast().x-p.x)*(p.y-min.y)==0)tail.add(p);
30 	Collections.sort(tail, new Comparator<Point>(){
31 		public int compare(Point p0, Point p1) {
32 			return Double.compare(min.distance(p1),min.distance(p0));
33 		}
34 	});
35 	out.removeLast();
36 	out.addAll(tail);*/
37 	return new ArrayList<Point>(out);
38 }