[알고리즘] 볼록 껍질 (Convex Hull)

볼록 껍질은 2차원 상에 점들이 여러 개 있을 때

그것들 중 일부를 선택하여 나머지 점들을 모두 포함하는 볼록 다각형이다.

 

볼록 껍질을 구하는 방법은 여러 가지가 있지만

주로 O(NlogN)의 시간복잡도를 가지는 그라함 스캔(Graham's scan) 알고리즘을 사용한다.

---

다음과 같이 점들이 있다고 하자.

시작할 때 보통 가장 밑에 있는 점을 시작점으로 한다.

그러한 점이 여러 개 있을 때 가장 왼쪽의 점을 선택한다.

선택한 점부터 시작하여 반시계 방향으로 진행한다. (시계 방향도 가능함)

---

먼저 시작점으로부터 반시계방향으로 나머지 점들을 정렬해 준다.

스택에서 점들을 관리하여 Convex Hull를 만들어 줄 것이다.

스택의 최상단 점을 B, 그다음의 점을 A라고 하자.

벡터 AB에 대해 순회할 차례의 점이 왼쪽에 있는지 오른쪽에 있는지에 따라

점들을 관리할 것이다.

시작점과 1번 점을 스택에 넣고 시작한다.

---

이번에 순회할 점은 2번 점이다.

벡터 01에 대해 2번 점이 왼쪽에 있으니 스택에 넣는다.

---

이번에 순회할 점은 3번 점이다.

벡터 12에 대해 3번점이 오른쪽에 있으니 스택에서 2번점을 빼줘야 한다.

그러면 다시 벡터 01에 대해 3번점은 왼쪽에 있으니 스택에 넣는다.

---

이번에 순회할 점은 4번 점이다.

벡터 13에 대해 4번 점이 왼쪽에 있으니 스택에 넣는다.

---

이번에 순회할 점은 5번 점이다.

벡터 34에 대해 5번점이 오른쪽에 있으니 스택에서 4번점을 빼줘야 한다.

그러면 다시 벡터 13에 대해 5번점은 왼쪽에 있으니 스택에 넣는다.

---

이번에 순회할 점은 6번 점이다.

벡터 35에 대해 6번 점이 왼쪽에 있으니 스택에 넣는다.

---

모든 점을 순회하였고 Convex Hull이 만들어졌다.

(점들을 정렬했으므로 0번 점은 벡터 56에 대해 왼쪽에 있는 것이 당연하다)

---

정리해 보자.

 

1. 점들 중 가장 밑에 있는 점을 시작점으로 정한다. 그러한 점이 여러 개 있을 경우 가장 왼쪽의 점을 시작점으로 정한다.

2. 시작점에 대해 반시계 방향으로 점들을 정렬한다.

3. 스택에 0번 점과 1번 점을 넣는다.

4. 2번 점부터 순회를 시작한다.

5. 다음 순회할 점이 벡터 AB(이 글의 시작 부분에 정의한 벡터)에 대해 왼쪽이면 스택에 넣는다.

6. 왼쪽이 아닐 경우 왼쪽인 경우가 나올 때까지 스택에서 하나씩 뺀다. (단, 스택의 크기는 항상 2 이상이어야 한다)

    *같은 직선 위에 존재할 경우에는 Convex Hull에서 그 점은 큰 의미가 없기 때문에 그 점도 포함하지 않는다.

7. 모든 순회가 끝나면 Convex Hull이 만들어진다.

 

아래 링크의 문제는 볼록 껍질을 이루는 점들의 개수를 구하는 문제이다.

최종적으로 볼록 껍질을 구해준 뒤 스택의 사이즈를 구해주면

볼록 껍질을 이루는 점들의 개수를 구할 수 있다.

(스택의 원소들은 볼록 껍질을 이루는 점들이다)

https://www.acmicpc.net/problem/1708

1708번: 볼록 껍질

코드로 구현해보면 다음과 같다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct spot{ll x,y;};
ll CCW(spot a, spot b, spot c){
    return (a.x*b.y+b.x*c.y+c.x*a.y)-(b.x*a.y+c.x*b.y+a.x*c.y);
}
vector<spot> v;
bool cmp1(spot a, spot b){
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}
bool cmp2(spot a, spot b){
    ll ccw=CCW(v[0],a,b);
    // ccw값이 음수면 시계 방향
    // ccw값이 0이면 같은 직선 상에 존재
    // ccw값이 양수면 반시계 방향
    if(ccw) return ccw>0;
    return cmp1(a,b);
}

ll stk[100100], top, n;
void push(ll val){
    stk[top++] = val;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    v.resize(n);
    for(auto &[x,y] : v)
        cin>>x>>y;
    // 1. 시작점을 정한다.
    sort(v.begin(),v.end(),cmp1);
    // 2. 시작점에 대해 반시계 방향으로 점들을 정렬한다.
    sort(v.begin()+1,v.end(),cmp2);
    // 3. 스택에 0번 점과 1번 점을 넣는다.
    push(0); push(1);
    // 4. 2번 점부터 순회를 시작한다.
    for(ll i=2; i<n; i++){
        // 6. 왼쪽이 아닐 경우 왼쪽인 경우가 나올 때까지 스택에서 하나씩 뺀다.
        while(top>=2 && CCW(v[i],v[stk[top-2]],v[stk[top-1]])<=0)
            top--;
        // 5. 다음 순회할 점이 벡터 AB에 대해 왼쪽이면 스택에 넣는다.
        push(i);
    }
    // 7. 모든 순회가 끝나면 Convex Hull이 만들어진다.
    cout << top;
    return 0;
}

볼록 껍질을 구해서 뭐 하는 데에 쓰이는가 하면

dp최적화(Convex Hull Trick), 가장 먼 거리의 두 점 구하기(rotating calipers)

더 많이 있겠지만 저 두 개가 가장 많이 쓰인다.

 

+) 2차원 말고도 3차원에서의 볼록 껍질도 있는 것 같다.