[알고리즘] Convex Hull (볼록외피) - Graham's Scan (그라함 스캔) (C++로 구현하기)

Convex Hull 이란?

Convex Hull은 우리말로 번역하면 '볼록외피' 라는 뜻입니다.

말로는 잘 이해되지 않으니, 다음 그림을 보며 설명드리겠습니다.

7개의 노드가 있습니다.

여기에서, 가장 바깥의 노드들로만 전체를 감싸면, 그것이 Convex Hull이 됩니다.

아래와 같이 말이죠.

이러한 Convex Hull을 구하는 알고리즘은 여러가지 종류가 있습니다.

Graham's Scan, Andrew Algorithm 등이 있는데,

오늘 여기에서는 Graham's Scan 알고리즘에 대해서 알아보겠습니다.

 

 

 

동작 원리

Convex Hull을 구현하기에 앞서,

계산기하학에서 자주 사용되는 CCW (Counter Clock Wise) 라는 용어에 대해 이해할 필요가 있습니다.

 

우리는 3개의 노드가 있을 때, 이 노드를 잇는 선이

좌회전하는지, 우회전하는지 어떻게 판단할 수 있을까요? 아래 그림을 보시죠.

 

노드 1 에서 노드 2로,

노드 2 에서 노드 3으로

연결했을 때, 선분은 좌회전합니다.

그렇다면 아래의 그림을 보시죠.

 

이 경우는 어떤가요?

위와는 다르게, 선분이 우회전함을 알 수 있습니다.

 

그렇다면 우리는 이렇게 3개의 노드가 주어졌을 때,

선분이 좌회전하는지, 우회전하는지를 어떻게 판단할 수 있을까요?

 

이에 대한 해답이 바로 CCW 입니다.

CCW는 벡터 값으로 표현한 노드들에 대해서 외적 (Outer Product) 을 수행한 값입니다.

 

이 때, 외적한 값에 따라 다음의 판단이 가능합니다.

 

1) CCW(1, 2, 3) > 0 : 좌회전 (Left Turn)

2) CCW(1, 2, 3) < 0 : 우회전 (Right Turn)

3) CCW(1, 2, 3) = 0 : 3개의 노드가 일직선상에 있음

 

이 CCW에 대해서 이해했다면, 이 알고리즘의 절반은 이해한 것입니다.

 

 

그렇다면 본격적으로 Convex Hull 에 대해서 알아보겠습니다.

이 Convex Hull 을 보시면 재밌는 규칙 하나를 찾을 수 있습니다.

반시계 방향으로 보면, 모든 선분들이 좌회전한다는 것입니다.

이러한 특징을 이용해서 모든 노드들에 대해서 선분이 좌회전하는 것만 고르면 됩니다.

 

즉, 다음의 순서를 이용해 Convex Hull을 찾을 수 있습니다.

 

1) 기준점을 찾는다.

- 일반적으로, 가장 Y좌표가 낮은 (같다면 X좌표가 낮은) 점을 기준으로 합니다.

 

2) 모든 노드를 기준점에 대해 반시계 방향으로 정렬합니다.

- CCW 값을 이용해 가능합니다.

 

3) 기준점부터 시작해서, 순서대로 모든 노드에 대해서 좌회전 여부를 검사합니다.

- 좌회전에 해당하는 선분만 찾으면, 그것이 바로 Convex Hull 입니다.

 

 

다음은 상세한 동작 순서입니다.

가장 먼저, 기준점을 잡고 그 기준점을 대상으로 모든 노드를 반시계 방향으로 정렬합니다.

아래와 같이 말입니다.

그리고 스택을 이용해서, 좌회전 여부를 검사합니다.

 

처음 단계입니다.

0 ~ 2를 잇는 선분이 좌회전하였으므로, 이를 스택에 넣습니다.

 

하지만 다음으로,

1 ~ 3을 잇는 선분이 우회전하였으므로, 

노드 2는 Convex Hull이 아닙니다. 스택에서 제외합니다.

 

다음으로,

0 - 1 - 3 을 잇는 선분이 좌회전 하였으므로, 스택에 넣습니다.

 

이런 식으로 모든 노드들에 대해서 반복하면,

결과적으로 아래와 같이 Convex Hull을 얻을 수 있습니다.

 

 

 

 

구현 (C++)

#include <iostream>

#define	MAX_POINT	100000

using namespace std;

typedef long long ll;

typedef struct Point {
	int x;
	int y;
	bool operator<(const Point& p) {
		if (y != p.y) return x < p.x;
		else return y < p.y;
	}
	Point operator-(const Point& p) {
		Point ret = { x - p.x, y - p.y };
		return ret;
	}
} Point;

Point p[MAX_POINT];
int stack[MAX_POINT];
int N;

ll ccw(Point &A, Point &B, Point &C) {
	Point BO = B - A;
	Point CO = C - A;
	return 1LL * ((ll)BO.x * (ll)CO.y - (ll)BO.y * (ll)CO.x);
}
bool leftTurn(Point& A, Point& B, Point& C) { return ccw(A, B, C) > 0; }

bool comp(Point &A, Point &B)
{
	Point AO = A - p[0];
	Point BO = B - p[0];

	ll outerProduct = 1LL * ((ll)AO.x * (ll)BO.y - (ll)AO.y * (ll)BO.x);
	if (outerProduct != 0)
		return (outerProduct > 0);
	if (A.y != B.y)
		return A.y < B.y;
	return A.x < B.x;
}

void quickSortByAngle(int first, int last)
{
	if (first >= last) return;

	int pivot = first;
	int i = first + 1;
	int j = last;

	while (i <= j)
	{
		while (comp(p[i], p[pivot]) && i <= last) i++;
		while (!comp(p[j], p[pivot]) && j > first) j--;

		if (i >= j) break;

		Point tmp = p[i];
		p[i] = p[j];
		p[j] = tmp;
	}

	Point tmp = p[j];
	p[j] = p[pivot];
	p[pivot] = tmp;

	quickSortByAngle(first, j - 1);
	quickSortByAngle(j + 1, last);
}

int convexHull()
{
	int minX = 1000000000, minY = 1000000000, minIdx = 0;;
	for (int i = 0; i < N; i++) {
		if (minY > p[i].y || (minY == p[i].y && minX > p[i].x))
		{
			minX = p[i].x;
			minY = p[i].y;
			minIdx = i;
		}
	}
	p[minIdx].x = p[0].x;
	p[minIdx].y = p[0].y;
	p[0].x = minX;
	p[0].y = minY;

	quickSortByAngle(1, N - 1);

	int idx = -1;
	stack[++idx] = 0;
	stack[++idx] = 1;

	int next = 2;
	while (next < N)
	{
		while ((idx + 1) >= 2)
		{
			int second = stack[idx--];
			int first = stack[idx];

			if (leftTurn(p[first], p[second], p[next]))
			{
				stack[++idx] = second;
				break;
			}
		}

		stack[++idx] = next++;
	}

	return idx + 1;
}

int main(void)
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> p[i].x >> p[i].y;

	cout << convexHull() << '\n';

	return 0;
}