[기하] 회전하는 캘리퍼스 (Rotating calipers)

회전하는 캘리퍼스(Rotating calipers)
가장 먼 두점의 거리 구할때 사용하는 알고리즘

출처 : https://en.wikipedia.org/wiki/Rotating_calipers

 

컨벡스헐을 구한 다음에 수행해야한다.
자세한 원리는 위키(https://en.wikipedia.org/wiki/Rotating_calipers)에서 확인할 수 있다.
컨벡스헐 전체 거리를 볼 필요가 없기 때문에 빠르다.

자바로 구현한 코드

	// Previous, should make convexHull
	long maxDist = 0;
	long a1=0, a2=0, a3=0, a4=0;
	int j = 1;
	for(int i=0; i<convexHull.size(); i++) {
	int i_next = (i+1) % convexHull.size();
	for(;;) {
	int j_next = (j+1) % convexHull.size();
	long bx = convexHull.get(i_next).x - convexHull.get(i).x;
	long by = convexHull.get(i_next).y - convexHull.get(i).y;
	long cx = convexHull.get(j_next).x - convexHull.get(j).x;
	long cy = convexHull.get(j_next).y - convexHull.get(j).y;
	int ccw = ccw(0, 0, bx, by, cx, cy);
	if(ccw > 0) j = j_next;
	else break;
	}
	long dist = dist(convexHull.get(i), convexHull.get(j));
	if(dist > maxDist) {
	maxDist = dist;
	a1 = convexHull.get(i).x;
	a2 = convexHull.get(i).y;
	a3 = convexHull.get(j).x;
	a4 = convexHull.get(j).y;
	}
	}
	System.out.println(a1 + " " + a2 + " " + a3 + " " + a4);

view raw RotatingCallipers.java hosted with ❤ by GitHub