컨벡스 헐 (Convex hull: 볼록 껍질), 그라함 스캔, CCW / 기하학

컨벡스 헐(Convex hull) 이란?

한글로는 볼록 껍질이라고 한다. 2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이것이 볼록 껍질이다. N = 10 이라고 할 때 한 예는 아래 사진과 같다.

그라함 스캔?

볼록 껍질(컨벡스 헐)을 만들 때 유명한 알고리즘이 그라함 스캔 알고리즘이다.

아래는 그라함 스캔으로 컨벡스 헐을 만드는 시뮬레이션 영상이다.

Graham Scan: find the convex hull of a point set

1. 가장 y가 작은 점을 구한다. (동영상에서는 시작 점인 7이 y가 가장 작은 점이다.)
2. 그 점을 기준으로 직선의 각을 기준으로 정렬한다.
3. 각이 가장 작은 점부터 조사하면서 볼록 껍질인지 아닌지 확인하고 추가한다.

마지막으로, CCW가 뭘까?

그라함 스캔 알고리즘 과정에서 새로운 점 연결 여부를 판별하는데 사용된다.

세 점이 있을 때 반시계 방향으로 움직이는지, 시계방향으로 움직이는지 찾는 알고리즘이다.

CCW는 점 A,B,C를 순서대로 봤을때 반시계방향으로 놓여 있으면 양수를, 시계방향이면 음수를, 평행하게 놓여있으면 0을 반환한다. 

위 사진 처럼 $\vec{a}=\vec{AB}$, $\vec{b}=\vec{AC}$로 놨을 때, 세 점의 방향관계는 $\vec{a}$와 $\vec{b}$의 외적의 방향으로 판별할 수 있다. (점 A, B 기준으로 점 C가 어느 방향에 있는지 판별)

외적을 구하는 자세한 방법을 알고 싶다면, degurii.tistory.com/47 블로그의 2번부터 읽어보면 좋다.

그래서 세 점의 방향관계를 반환하는 ccw 함수는 아래와 같다.

private static class Pos {
	int x;
    int y;
    
    public Pos(int x, int y) {
    	this.x = x;
        this.y = y;
    }
}

private static int ccw(Point A, Point B, Point C) {
	return (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
}

•  반환 값 > 0  점 A, B 기준으로 C가 반시계 방향에 위치한다.
•  반환 값 == 0  점 A, B 기준으로 C가 평행하게 위치한다.
•  반환 값 < 0  점 A, B 기준으로 C가 시계 방향에 위치한다.

 

이들을 활용해서 풀어 볼 수 있는 문제 : BOJ 1708 볼록 껍질

 

참고

1. degurii.tistory.com/47
2. beenlife.tistory.com/57
3. www.crocus.co.kr/1288