반응형


목차


1. 컨벡스 헐 알고리즘(Convex Hull Algorithm)이란?


2. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 동작 원리


3. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 구현


4. 관련 문제




1. 컨벡스 헐 알고리즘(Convex Hull Algorithm)이란?



컨벡스 헐 알고리즘은 2차원 평면상에 여러개의 점이 있을 때 

그 점 중에서 일부를 이용하여 볼록 다각형을 만들되 볼록 다각형 내부에 모든 점을 포함시키는 것을 의미한다.


즉, 아래 그림과 같게 된다.



이러한 것을 볼록 껍질이라 하고 현재 볼록 껍질은 5개의 점으로 이루어져있고 2차원 평면상의 점을 모두 포함하고 있다.


이제 이러한 볼록 껍질을 구하는 알고리즘을 구현해 볼 것인데, 


O(NlgN)에 해결 할 수 있는 그라함 스캔(Graham's Scan) 알고리즘을 알아보도록 한다.


(시간 복잡도는 결국 정렬에 영향을 받게 된다.)





2. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 동작 원리


간단하게 컨벡스 헐 알고리즘을 구현하기 전 전처리는 다음과 같다.


1. 우선 기준점을 잡는다. (보통 기준점은 y좌표가 가장 작은 것을 기준으로 한다.)


2. 그리고 이 기준점으로 하여 다른 점들을 반시계 방향으로 정렬한다.

(각에 따라 정렬하면 된다.)


3. 컨벡스 헐 알고리즘(그라함 스캔(Graham's Scan) 알고리즘)을 이용한다.


이제 컨벡스 헐 알고리즘이 어떻게 돌아가는지 그림으로 파악해보자.



우선 스택에 첫번째 정점과 두번째 정점에 해당하는 값을 스택에 넣고 시작한다.



스택에서 second와 first를 순서대로 꺼내고 next값과 ccw를 하여 > 0인지 확인한다(좌회전 하는지 확인)


이때 좌회전을 한다면 ( > 0 이라면 ) 볼록 껍질이 될 수 있다는 의미이고 


pop했던 second를 다시 스택에 넣어주고 next를 스택에 넣어준다.



그다음으로 다시 second와 first 순으로 스택에서 꺼내고 next와 ccw를 해본다.


이때도 좌회전이니 ( > 0 ) 스택에 second와 next를 넣어주고 진행한다.



이번에는 first, second, next의 ccw가 우회전( < 0 )이다.


따라서 pop했던 second를 넣어주지 않고 다시 진행해본다.


다시 진행한다는 의미는 스택에는 위의 second점은 이제 없고 아래 그림과 같이 first점이 second가 되는 상태가 된다.

  


first, second, next를 ccw하면 좌회전 ( > 0 )이다.


따라서 스택에 second와 next를 넣어준다.


이번에는 first와 second, next를 ccw 하니 우회전이다. 따라서 이전 상태로 돌아가서 다시 본다.


좌회전이므로 스택에 second와 next를 넣는다.



좌회전이므로 스택에 second와 next를 넣는다.



이번에는 first와 second, next를 ccw 하니 우회전이다. 따라서 이전 상태로 돌아가서 다시 본다.


좌회전이므로 스택에 second와 next를 넣는다.



최종적으로 위와 같이 볼록 껍질을 만들어 낼 수 있다.



이때 ccw가 < 0 이라면 즉, 우회전이라면 위의 그림에서는 한번만 이전상태로 돌아갔는데 first, second, next의 ccw가 > 0이 될때까지 계속해서 반복해주면 된다.




부록)


아래는 Quick Hull인데 가장 왼쪽 위, 가장 오른쪽 아래 두 점을 잡고 그 선분을 이었을 때 선분과 가장 먼 거리의 점을 잡아


총 3개의 점이 생기면 그 삼각형 내부에 있는 점은 볼록 껍질 후보가 될 수 없다는 사실로 시작한다.


File:Animation depicting the quickhull algorithm.gif







3. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 구현


[1708번] 볼록 껍질 :: https://www.acmicpc.net/problem/1708


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
 
#define MAX 100002
 
using namespace std;
 
typedef long long ll;
 
struct INFO {
    int x, y;
    int p, q;
    INFO(int x1 = 0int y1 = 0) : x(x1), y(y1), p(1), q(0) {}
};
 
bool comp(const INFO &A, const INFO &B) {
    if (1LL * A.q * B.p != 1LL * A.p*B.q)
        return 1LL * A.q * B.p < 1LL * A.p*B.q;
 
    if (A.y != B.y)
        return A.y < B.y;
 
    return A.x < B.x;
}
 
ll ccw(const INFO &A, const INFO &B, const INFO &C) {
    return 1LL * (A.x * B.y + B.x * C.y + C.x * A.y - B.x * A.y - C.x * B.y - A.x * C.y);
}
 
INFO p[MAX];
 
int main() {
    int n;
    scanf("%d"&n);
 
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d"&x, &y);
 
        p[i] = INFO(x, y);
    }
 
    // y좌표, x좌표가 작은 순으로 정렬
    sort(p, p + n, comp);
 
    // 기준점으로부터 상대 위치 계산
    for (int i = 1; i < n; i++) {
        p[i].p = p[i].x - p[0].x;
        p[i].q = p[i].y - p[0].y;
    }
 
    // 반시계 방향으로 정렬(기준점 제외)
    sort(p + 1, p + n, comp);
 
    stack<int> s;
 
    // 스택에 first, second를 넣어준다.
    s.push(0);
    s.push(1);
 
    int next = 2;
 
    while (next < n) {
        while (s.size() >= 2) {
            int first, second;
            second = s.top();
            s.pop();
            first = s.top();
 
            // first, second, next가 좌회전 ( > 0 )이라면 second push
            // 우회전( < 0 )이라면 위의 while문 계속 반복
            if (ccw(p[first], p[second], p[next]) > 0) {
                s.push(second);
                break;
            }
        }
 
        // next push
        s.push(next++);
    }
 
    printf("%d", s.size());
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





4. 관련 문제


http://www.crocus.co.kr/search/%EC%BB%A8%EB%B2%A1%EC%8A%A4%20%ED%97%90








반응형

'Applied > 알고리즘' 카테고리의 다른 글

GCD, LCM STL  (2) 2018.10.04
편집거리 알고리즘  (2) 2018.06.29
백트래킹을 이용한 순열, 조합, 중복순열, 중복조합  (5) 2018.04.28
확장 유클리드 알고리즘  (2) 2018.04.18
모듈러 연산(Modular Arithmetic)  (8) 2018.04.18