볼록껍질(Convex Hull)
여러 점들이 막 주어져 있을때 모든 점을 포함하는 볼록한 다각형을 의미한다. 볼록 껍질에에서 연속한 세 점을 한 쪽 방향으로 잡으면 모든 결과가 같다는 것을 이용하여, CCW 방식으로 구할 수 있다.
볼록껍질을 구하는 대표적인 알고리즘인 Graham Algorithm은 점들을 정렬하는데에서 시작한다.
- 볼록껍질에 무조건 들어가는 점 하나를 잡는다. (보통 가장 x좌표가, y좌표가 작은 점)
- 그 점을 기준으로 기울기 순으로 정렬한다. 같은 기울기면 거리 순으로 정렬.
- 점들을 그룹에 순서대로 넣는다.
- 넣으면서 그룹의 제일 최근 3점의 ccw가 옳지 않으면 그 세 점 중 중간 점을 뺀다.
- 3~4를 반복하면서 1번점까지 돌아온다.
코드로 구현하면 아래처럼 된다.
vector<point> convex_hull(vector<point>& points) { int n = points.size(); if(n <= 3) return points;
for (int i=1;i<n;i++) { if (points[i].y < points[0].y || (points[i].y == points[0].y && points[i].x < points[0].x)) { swap(points[i], points[0]); } }
sort(points.begin()+1, points.end(), [&](point &a, point &b) { return cmp(a, b, points[0]); });
vector<point> hull; hull.push_back(points[0]); hull.push_back(points[1]); for(int i=2;i<n;i++) { while(hull.size()>=2&& ccw(hull[hull.size()-2], hull.back(), points[i]) <= 0) hull.pop_back(); hull.push_back(points[i]); } return hull;}회전하는 캘리퍼스
캘리퍼스는 길이를 재는 도구이다. 회전하는 캘리퍼스는 놓여있는 점들 중 가장 먼 두 점의 거리를 구할때 돌면서 구하겠다는 뜻이다. two pointer 기반으로 이루어진다.
일단 점들중 가장 거리가 먼 두 점이 있다면 그 두 점은 모두 볼록 껍질 위에 있다라는 사실을 전제로 한다. 완벽히 증명은 되지 않아도 어느정도 직관적으로 이해할 수 있는 사실이다. 따라서 전체 점에서 볼록껍질을 잡고 시작한다. 볼록껍질에서 가장 먼 두 점 사이의 거리를 구하는 과정은 다음과 같이 이루어진다.
- 다각형의 한 점을 l, 다른 점을 r이라고 하자.
- l의 다음 점을 nl, r의 다음 점을 nr라고 하자.
- l과 r의 거리를 잰다.
- 벡터 l-nl와 벡터 r-nr의 CCW를 이용해 두 벡터가 정반대에 가까워지도록 l나 r을 한칸 돌린다.
- l이 처음으로 올때까지 반복한다.
가장 먼 점
회전하는 캘리퍼스 알고리즘으로 다각형에서 가장 먼 두 점의 거리를 구하는 문제로는 #9240, #10254, #1310, #8927 등이 있다.
위에서 설명한 방식을 그대로 구현하면 된다.
ld rotatingCalipers(vector<point>& p) { ll n = p.size(); int l=0, r=1; double res = hypot(p[l]-p[r]);
for (int t=0;t<n*2;t++){ int nl=(l+1)%n, nr=(r+1)%n;
double tmp = ccw(p[nl]-p[l], p[r]-p[nr]); if (tmp>0) l=nl; else if (tmp<0) r=nr; else if (tmp==0) { l=nl; r=nr; }
res=min(res, hypot(p[l]-p[r])); } return res;}점에서 가장 먼 변
회전하는 캘리퍼스 알고리즘으로 다각형에서 특정 점에서 가장 먼 변의 거리를 구하는 문제로는 #15028, #15420 등이 있다. 다각형을 어떤 구멍에 넣을 때 필요한 최소 폭을 구하는 문제가 많다.
점에서 가장 먼 변을 구할 때는 ccw가 0보다 큰 경우 l을 움직이고, 그렇지 않은 경우 r을 움직이면서 선분(l, nl) 또는 (r, nl)과 반대 점의 거리 최솟값을 구하면 된다.
ld rotating_calipers(vector<point>& hull) { ll n=hull.size(); if (n<=2) return 0;
ll l=0, r=0; for (int i=0;i<n;i++) { if (p[i].x<p[l].x) l=i; if (p[i].x>p[r].x) r=i; }
ld res = numeric_limits<ld>::max(); point o = {0, 0}; for (int i=0;i<n;i++) { ll nl = (l+1)%n, nr=(r+1)%n; if (ccw(o, p[nl]-p[l], p[r]-p[nr]) > 0) { res = min(res, dist(p[l], p[nl], p[r])); l = nl; } else { res = min(res, dist(p[r], p[nr], p[l])); r = nr; } } return res;}볼록다각형을 포함하는 가장 작은 직사각형
회전하는 캘리퍼스를 응용해 볼록다각형을 포함하는 가장 작은 직사각형을 구하는 문제를 해결할 수 있다. 이 방식을 사용하는 대표적인 문제로는 #19586, #9276, #10466가 있다.
볼록다각형을 포함하는 가장 작은 직사각형은 항상 해당 다각형의 한 변을 포함하는 원리를 활용한다. 우선 Convex Hull을 구한 뒤, Convex Hull의 각 변에 대한 반대쪽 점(u), 왼쪽(l), 오른쪽(r) 점을 각각 구해서 너비를 구하면 된다.
반대쪽 점은 점에서 가장 먼 변을 구하는 것과 동일한 방식으로 구하고, 왼쪽, 오른쪽 점은 기준 변과 r에서 다음 점으로의 변의 방향을 추가로 비교하여 구한다.
ld rotatingCalipers(vector<point>& p) { if (n==1) { return 0; } if (n==2) return 2*sqrt(dist(p[0], p[1]));
auto chk = [&cx, &n](int i, int j){ return (p[(i+1)%n]-p[i])/(p[(j+1)%n]-p[j])>0; };
int u=1, l=1, r=1; ld res = numeric_limits<ld>::max(); for (int i=0;i<n;i++){ if (u==i) u=(u+1)%n; while (chk(i,u)) u=(u+1)%n; if (l==i) l=(l+1)%n; while (chk(i,l)||(p[(i+1)%n]-p[i])*(p[(l+1)%n]-p[l])<0) l=(l+1)%n; if (r==i) r=(r+1)%n; while (chk(i,r)&&(p[(i+1)%n]-p[i])*(p[(r+1)%n]-p[r])>0) r=(r+1)%n;
point v1 = p[(i+1)%n]-p[i], v2 = {v1.y,-v1.x}; res = min(res, 2*((ld) dist(p[i], p[u], v1) + (ld) dist(p[l], p[r], v2))); } return res;}참고
