×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,791,955명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형


목차


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
  1. thanks 2019.04.12 17:36

    도움 많이 되었습니다. 감사합니다.

  2. 안녕하세요. 질문이 있습니다.

    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;

    이 식이 어떻게 각을 기준으로 정렬하는 비교함수인지 모르겠습니다.
    제가 개인적으로 해볼 때는 cmath의 atan2()으로 직접 각을 계산해서 정렬했는데,
    기준점으로부터 상대 위치로 어떻게 정렬한 것인지 이해가 안됩니다.

    설명해주실 수 있나요?

    • 가누 2019.06.15 13:26 신고

      A.q/A.p < B.q/B.p 수식을 정리하여 도출한 결과이고 이는 tan함수를 이용했음을 알 수 있습니다,