컨벡스 헐(Convex Hull) 알고리즘

Convex Hull

 

 

2차원 좌표 평면에 여러 점이 존재하는 상황을 생각해보자. 이러한 점들을 다루는 2차원 평면은 너무 넓다. 다시 말해서, 탐색 범위나 관심을 가지는 구간을 2차원 평면 전체로 잡는 것은 너무 비효율적이며 관심 있는 구간을 설정하는 과정이 필요하다는 것이다.

Convex Hull은 점들이 포함되는 영역과 포함되지 않는 영역으로 2차원 좌표 평면을 나누어 줄 수 있는 도형이다. 즉, Convex Hull 안에는 점들이 모두 포함되지만, 밖의 영역에는 점들이 존재하지 않는 것이다.

 

 

Convex Hull은 2차원 좌표 평면에 존재하는 여러 점들 중 일부를 이용하여 만들 수 있는 모든 점을 포함하는 볼록 다각형이다. 점들을 이용하여 만든 도형이기에, 다른 말로 표현하면 모든 점을 포함하는 볼록 다각형 중, 면적이 최소인 다각형이다. 아래와 같이 점들이 2차원 좌표 평면에 존재할 때, 볼록 껍질을 나타내어보면 다음과 같다.

 

 

2차원 평면에 점이 존재한다.

 

 

 

Convex Hull

 

 

 

 

컨벡스 헐 알고리즘은 2차원 좌표 평면에서 점들의 좌표가 주어졌을 때 볼록 껍질을 구성하는 점들을 $O(N)$에 구하는 알고리즘으로(점을 정렬하는 등의 데이터 구성을 위한 전처리는 O(NlogN)이 소모된다), 다양한 알고리즘이 존재하는데, 이 중 Graham Scan이라는 알고리즘을 통해 볼록 껍질을 구할 것이다.

 

 

 

 

Graham Scan의 동작 과정은 다음과 같다.

 

 

 

1. 주어진 점들을 반시계방향으로 정렬하고, 정렬된 순서대로 점들을 탐색한다.

 

2. stack에 1번 점과 2번 점을 push한다.

 

3. 3번 ~ N번째 점까지 아래의 과정을 반복할 것이다.

 

• 만약 stack의 최상단에 있는 두 점을 이은 직선 l에 대해, 현재 탐색하는 점이 l의 왼쪽에 존재한다면 stack에 push한다.
• 그렇지 않다면 stack을 1번 pop하고 위 조건을 다시 확인한다.

4. 최종적으로 탐색이 끝나면 stack에는 Convex Hull을 구성하는 점들이 포함되어 있다.

 

 

---

 

 

볼록 껍질을 구성하는 점들을 구하기 위해서 특정 점에서 시작해서 반시계 방향으로 점들을 탐색할 것이다. 그러기 위해선 가장 아래에 있는 즉, y좌표가 가장 작고, 그들 중에서 x좌표가 가장 작은 점에서 탐색을 시작해야 한다. 탐색을 진행하면서 만약 현재 확인하고 있는 점이 볼록껍질에 포함된다면 해집합에 포함하고, 그렇지 않다면 포함시키지 않는다.

이를 수행하면서 생각해야할 것은, 해집합에 점을 포함시킬 때, 해당 점을 집합에 포함시켜도 현재 집합에 있는 점들이 이루고 있는 다각형이 볼록한지에 대한 확인이 필요하다. 그러므로 우리는 CCW라는 알고리즘(벡터의 외적)을 이용하여 세 점의 위치 관계를 확인할 것이다.

CCW 알고리즘(외적)은 3개의 점의 위치 관계를 알아내는 기하 알고리즘으로, 세 점이 일직선 상에 있으면 0, 반시계 방향이면 0보다 크고, 시계방향이면 0보다 작은 값을 반환한다.

 

 

---

 

 

How to Work

 

 

 

1. 점들을 반시계방향으로 정렬한다. 아래 그림은 $1$번 점을 기준으로 반시계방향으로 정렬한 것이다. 이 번호 순서대로 점들을 탐색할 것이다.

 

2. stack에 $1$, $2$번 점을 넣어준다. 그리고 $3$번째 점부터 탐색을 해주는데 만약 $i$번째 점이 stack 최상단에 있는 두 점을 이은 선분 l의 왼쪽에 있으면 stack에 넣어주고 아니면 stack을 pop한다. 위 그림에서 $1$, $2$번 점을 stack에 넣고 $3$번 점부터 계산을 해보면

 

 

 

$3$번 점은 $1$, $2$번 점을 이은 벡터의 왼쪽에 있으므로 stack에 $3$을 push한다.

 

$4$번 점은 $2$, $3$번 점을 이은 벡터의 왼쪽에 있으므로 stack에 push해준다.

 

 

$5$번 점은(Convex Hull에 속하지는 않지만 일단) $3$, $4$번 점을 이은 벡터의 왼쪽에 있으므로 stack에 push해준다.

 

 

$6$번 점은 $4$, $5$번 점을 이은 벡터의 오른쪽에 있으므로 stack을 pop해준다.

 

 

 

$6$번 점은 $3$, $4$번 점을 이은 벡터의 왼쪽에 있으므로 stack에 push해준다.

 

 

$7$번 점은 $4$, $5$번 점을 이은 벡터의 왼쪽에 있으므로 stack에 push해준다.

 

 

 

$N$번째 점까지 계산을 완료하면 stack에 들어있는 점들의 번호가 볼록 껍질을 구성하는 점들의 번호이고 stack의 크기가 볼록 껍질을 구성하는 점들의 개수이다.

 

 

6개의 점으로 구성된 Convex Hull

 

 

 

---

 

 

Implementation

 

 

위 동작 과정을 코드로 구현하면 아래와 같다. 이 때, Point 구조체는 < operator가 y좌표에 대한 대소 기준을 제공하도록 하여 sort를 했을 때, 가장 왼쪽 아래에 있는 점이 첫 번째 점이 되도록 한다. 또한 정렬 기준 compare 함수는 점들이 ccw > 0을 유지하는 순서로 존재하도록 하여 반시계 방향으로 정렬될 수 있도록 한다. 정렬 이후의 과정은 위의 동작 과정과 동일하며, 구현의 편의성을 위해 stack을 Array로 사용했음을 유의하라.

 

#include <iostream>
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int N;
 
struct Point{
    ll x, y;
    bool operator < (const Point &a){
        return y==a.y ? x<a.x : y<a.y;
    }
};
Point p[100001];
 
ll ccw(const Point &a, const Point &b, const Point &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;
}
 
ll dist(Point a, Point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
 
bool cmp(const Point &a, const Point &b)
{
    ll c=ccw(p[0], a, b);
    //점이 직선 상에 있으면 가까운 점을 먼저
    if(c==0){
        return dist(p[0], a)<dist(p[0], b);
    }
    return c>0;
}
 
 
 
int st[100001], top;
void push(int n){ st[top++]=n; }
 
 
int main()
{
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        scanf("%lld %lld", &p[i].x, &p[i].y);
    }
    //y좌표 기준으로 정렬
    sort(p, p+N);
    //가장 왼쪽에 있는 점을 기준으로 반시계방향 정렬
    sort(p+1, p+N, cmp);
    push(0);
    push(1);
    for(int i=2; i<N; i++){
        while(top>=2 && ccw(p[i], p[st[top-2]], p[st[top-1]])<=0) top--;
        push(i);
   }
    printf("%d\n", top);
    return 0;
}