볼록 껍질(Convex Hull)

볼록 껍질, Convex Hull?

2차원 평면 위에 N개의 점들이 있을 때, N개의 점을 모두 에워싸는 가장 작은 볼록 다각형으로 그림과 같다.

Convex Hull

일반적으로 Convex Hull을 구하기 위해, 모든 점들을 서로 비교해가면서 모든 경우를 구해 볼 수 있다.

하지만 이 경우 점의 개수가 10,000 개만 넘어가도 엄청난 시간이 소요된다.

 

그레이엄 스캔, Graham Scan

볼록 껍질을 구하는 알고리즘으로, O(nlogn)의 시간에 Convex Hull을 구할 수 있다.

* 선행 알고리즘 : CCW, Counter Clockwise

3개의 점의 위치 관계를 알아내는 기하 알고리즘, 세 점이 일직선 상에 있으면 0, 반시계 방향이면 양수, 시계 방향이면 음수를 반환한다.

 

그레이엄 스캔 알고리즘 과정

1. 주어진 점들을 반시계 방향으로 정렬하고, 정렬된 순서대로 점들을 탐색(보통 x 좌표 기준으로 정렬)

2. 처음 1, 2, 3번 점이 기준이 된다.

3. 스택에 1번과 2번점을 push

4. 3번 ~ N번 점까지 아래의 과정을 반복

- 만약 스택의 top에 있는 두 점을 이은 직선에 대해, 현재 탐색하는 점이 왼쪽에 존재한다면 스택에 push

- 그렇지 않다면 stack을 pop하고, 다시 위의 조건을 확인

 

 

 

1. 주어진 점들을 반시계 방향으로 정렬한다.

 

2. 첫번째 점과 두번째 점이 스택에 push한 채로 세번째 점부터 탐색한다.

세 점의 관계가 반시계 방향이룬다. push

 

3. 마찬가지로 반시계 방향이룬다. push

 

4. 마찬가지로 반시계 방향을 이룬다. push

 

5. 세 점(4, 5, 6)번째 점이 시계  방향을 형성한다. pop

 

6. 세 점(3, 4, 6)번째 점끼리는 반시계 방향을 이룬다. push

 

7. 마찬가지로 반시계 방향을 이룬다. push

 

8. 세 점이 시계 방향을 이룬다. pop

 

9. 다시 push

 

10. 스택에 쌓여있는 점들을 모두 연결하면 Convex Hull을 이룬다.

 

 코드

CCW계산, 정렬을 위한 cmp함수

백준: 그레이엄 스캔 알고리즘을 활용한 볼록 껍질 문제 : https://www.acmicpc.net/problem/1708

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;
struct Dot {
    long long x, y;
};
vector<Dot> v;
int N;
stack<Dot> answer;
int cross(Dot a, Dot b, Dot c)
{
    // a > b > c
    Dot l1 = { b.x - a.x, b.y - a.y };
    Dot l2 = { c.x - b.x, c.y - b.y };
    long long r = l1.x * l2.y - l1.y * l2.x;
    if (r < 0) return -1;
    else if (r > 0) return 1;
    return 0;
}
long long getDistance(Dot a)
{
    return (v[0].x - a.x) * (v[0].x - a.x) + (v[0].y - a.y) * (v[0].y - a.y);
}
bool cmp(Dot a, Dot b) {
    int r = cross(v[0], a, b);
    if (r > 0) return 1;
    else if (r == 0) return getDistance(a) < getDistance(b);
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    int a, b, tmp1, tmp2;
    cin >> a >> b;
    v.push_back({ a, b });
    for (int i = 1; i < N; ++i) {
        cin >> a >> b;
        if (a < v[0].x) {
            tmp1 = v[0].x;
            tmp2 = v[0].y;
            v[0] = { a, b };
            v.push_back({ tmp1, tmp2 });
        }
        else if (a == v[0].x && b < v[0].y) {
            tmp1 = v[0].x;
            tmp2 = v[0].y;
            v[0] = { a, b };
            v.push_back({ tmp1, tmp2 });
        }
        else {
            v.push_back({ a, b });
        }
    }
    sort(v.begin() + 1, v.end(), cmp);
    // print
    //for (Dot i : v) cout << i.x << " " << i.y << "\n"; 
    answer.push(v[0]);
    answer.push(v[1]);
    for (int i = 2; i < N; ++i)
    {
        while (answer.size() >= 2) {
            Dot prev = answer.top();
            answer.pop();
            Dot prev2 = answer.top();
            if (cross(prev2, prev, v[i]) > 0) {
                answer.push(prev);
                break;
            }
        }
        answer.push(v[i]);
    }
    cout << answer.size();
    return 0;
 }