Graham Scan

2차원 좌표평면에 점들이 있을 때, 이들의 컨벡스 헐은 점들을 모두 포함하는 가장 작은 볼록다각형을 뜻한다. "점들이 있는 곳에 못을 박고, 바깥에 엄청 큰 고무줄을 놓았을 때 고무줄이 걸리는 점들"이라는 비유가 좋다. 꼭짓점이 점들의 부분집합이고, 모든 점을 포함하는 볼록다각형이면 컨벡스 헐이다.

 

컨벡스 헐, 정확히 "컨벡스 헐의 꼭짓점에 위치한 점들의 리스트"을 구하는 Graham Scan 알고리즘은 구현이 길지 않다:

sort(a, a+n);
sort(a+1, a+n, [](pint x, pint y) { return ccw(a[0], x, y) > 0 or (ccw(a[0], x, y) == 0 and dist(a[0], x) < dist(a[0], y)); });
 
t = 2;
for (int i=2; i<n; i++) {
    while (t>1 and ccw(r[t-2], r[t-1], a[i]) <= 0) t--;
    r[t++] = a[i];
}
 

 

다음은 이 알고리즘의 동작 원리를 설명하는 세 줄 요약..이라기 보다는 이 세 줄이 전부다.

 

1. 점들을 좌표 순서대로 정렬했을 때의 첫 정점은 무조건 컨벡스 헐의 꼭짓점을 이룬다. 즉, X좌표가 가장 작은 점들 중 Y좌표가 가장 작은 점을 찾아, 얘를 극점이라고 하자. 극점은 컨벡스 헐의 꼭짓점에 포함된다.

2. 나머지 $N-1$개의 점들을 극점에서 시작하는 벡터가 축과 이루는 각도 순으로 정렬한다. 각도가 같다면 2순위로 극점과의 거리의 오름차순이 되게 하자.

3. 정렬한 순서대로 $N-1$개의 점들을 차례로 보면서, 컨벡스 헐의 꼭짓점 리스트에 넣는다. 무조건 넣는다. 만약 새로운 점을 추가할 때 컨벡스 헐에 오목한 각이 생겨서 못 넣는다면, 오목한 각이 없어질 때까지 마지막으로 추가한 점들을 계속 빼서라도 기어코 넣는다.

 

 

일종의 그리디 알고리즘인데, 올바르게 작동함은 다음과 같이 증명한다. 말장난 같다.

 

 

• 수학적 귀납법을 쓰자. 극점을 $p_1$, 나머지 점을 각도 순으로 $p_{2..n}$이라 하자. $p_{1..i}$의 컨벡스 헐을 $C_i$라 하자. 물론 $S(C_1) = 0$임은 당연하다.

• Graham Scan 알고리즘으로 $C_{i-1}$까지를 올바르게 구했다고 하자. 이제 $C_i$를 구성하기 위해 $p_i$를 추가하려 한다. $p_i$는 $C_{i-1}$에 없으니까, $C_i$의 꼭짓점에 포함되어야 한다.

• $C_{i-1}$에다 $p_i$를 더해 다각형을 만들었는데, $p_i$와 직전에 추가한 두 점이 이루는 각 빼곤 다 볼록함을 알고 있다. 만약 새로 생긴 각이 오목하다면, 직전에 추가한 점을 제거해도 모든 점을 아직 포함하고 있다. 그 과정을 반복하다 보면 볼록해지고, 컨벡스 헐이 되고, $C_i$가 된다.

 

그리고 구현할 때 기억할 점. 기하 알고리즘이 다 그렇듯이 이상한 곳에서 뻑나기 십상이다.

 

1. 문제에서 한 직선 위에 여러 점이 있을 수 없다는 조건을 주지 않는 이상, 무조건 거리의 오름차순으로 정렬해야 한다. 까먹어도 대부분의 경우엔 상관 없지만, 첫 번째로 추가하는 점이 극점과 이루는 직선에 여러 점이 있을 때 오작동할 수 있다.

 

2. 위 6번 줄의 ccw 조건에서 등호를 빼면 180'의 내각을 이루는 꼭짓점도 모두 포함하게 된다. 즉 컨벡스 헐의 경계 위에 있는 모든 점을 구할 수 있게 된다. 문제에 따라서 알아서 쓰면 된다. 하지만 이 때에는 이 후처리를 잊으면 안 된다.

• 마지막 점($P_n$)이 극점($P_1$)과 이루는 직선 위의 점들은 거리가 감소하는 순서대로 추가되어야 한다. 따라서 모두 추가된 뒤에 이 점들의 순서를 뒤집는 처리를 해야 옳은 순서가 된다.

이를 포함한 "컨벡스 헐 위의 경계 위에 있는 모든 점을 구하는" 코드는 아래와 같다.

sort(a, a+n);
sort(a+1, a+n, [](pint x, pint y) { return ccw(a[0], x, y) > 0 or (ccw(a[0], x, y) == 0 and dist(a[0], x) < dist(a[0], y)); });
 
for (int i=n-1; i; i--) if (ccw(a[0], a[i], a[i-1])) {
    reverse(a+i, a+n);
    break;
}
 
t = 2;
for (int i=2; i<n; i++) {
    while (t>1 and ccw(r[t-2], r[t-1], a[i]) < 0) t--;
    r[t++] = a[i];
}
 

 

3. ccw 함수

int ccw(pint a, pint b, pint c) {
    lint k = a.x * (lint)b.y + b.x * (lint)c.y + c.x * (lint)a.y
            -a.y * (lint)b.x - b.y * (lint)c.x - c.y * (lint)a.x;
    if (k>0) return 1;
    if (k<0) return -1;
    return 0;
}