[기하] 컨벡스헐

컨벡스헐

 

기준점 잡기 -> 정렬 -> 컨벡스헐 만들기

 

 

	// 기준점
	for(int i=0; i<P.length; i++) {
	if(P[i].y < P[0].y || (P[i].y == P[0].y && P[i].x < P[0].x) ) {
	Point temp = new Point(P[0].x, P[0].y);
	P[0] = P[i];
	P[i] = temp;
	}
	}
	// 정렬
	Arrays.sort(P, new Comparator<Point>() {
	@Override
	public int compare(Point o1, Point o2) {
	int ccw = ccw(P[0].x, P[0].y, o1.x, o1.y, o2.x, o2.y);
	if(ccw > 0) return -1;
	else if(ccw < 0) return 1;
	else {
	long dist1 = dist(P[0].x, P[0].y, o1.x, o1.y);
	long dist2 = dist(P[0].x, P[0].y, o2.x, o2.y);
	if(dist1 < dist2) return -1;
	else if(dist1 > dist2) return 1;
	else return 0;
	}
	}
	});
	// 컨벡스헐
	Stack<Point> convexHull = new Stack<>();
	for(int i=0; i<P.length; i++) {
	while(convexHull.size() >= 2) {
	Point p1 = convexHull.get(convexHull.size()-2);
	Point p2 = convexHull.get(convexHull.size()-1);
	int ccw = ccw(p1.x, p1.y, p2.x, p2.y, P[i].x, P[i].y);
	if(ccw <= 0) convexHull.pop();
	else break;
	}
	convexHull.push(P[i]);
	}

view raw convexHull.java hosted with ❤ by GitHub