[알고리즘] Convex hull과 Graham's scan

1. Convex hull

---

Convex Hull이란, 점들로 구성된 Set을 모두 포함하는 외각 점들의 집합이다. 아래의 그림을 보자.

출처 : 위키피디아

검은 점들로 구성된 집합 `S`에서 어느 점을 선택하더라도, 파란색 선안에 포함되는 것을 알 수 있다. 이 파란색 선을 어떻게 찾아야 할까?

 

2. How to find convex hull

---

Convex Hull을 찾는 가장 간단한 방법은 각 점마다 모든 점들을 순회해서 가장 외각의 것을 선택하는 것이다. 하지만 이렇게 접근한다면, 결국 `O(n^2)`이 되어서 원하는 작업을 원할히 할 수 없다.

사실 모든 점을 순회한다는 것은 가장 외각의 점을 찾기 위함이다. 따라서 이 부분을 더욱 쉽게 만들어 준어야 한다.

 

 그런 방법들 중에서도, 외적을 이용한 `CCW`(Counter Clockwise) 방식을 주로 이용한다.

 

 외적이란 두 벡터 `x`, `y`에 대하여, `x_(x) * y_(x) + x_(y) * y(y)`으로 나타내어 진다. 이때 얻어지는 값은 벡터이며, 벡터는 항상 방향성을 가지기 때문에 외적의 값에 따라서 어느 벡터가 좌측인지 우측인지 알 수 있다.  모르겠으면, 손으로 풀어보자.

 

 아무튼 Graham Scan은 CCW를 이용하여, 시작점과, 점1 그리고 점2를 보면서 (`V_(1) = P1 - Start`, `V_(2) = P2 - Start`) 벡터 `V_(1)`과 벡터 `V_(2)`중에 어느 점이 가장 외곽에 있는지 확인한 다음 둘중 하나를 선택한다.

 

 사실 이렇게 동작하면 결국 다음 점을 선택하기 위해서 모든 점들을 다 확인해야 되기 때문에, `O(n^2)`이 된다.

 

 하지만 정렬을 CCW로 하게 되고 곧바로 가장 외각 점을 알 수 있게 된다면, Convex Hull을 찾는데는 `O(n)`만 걸릴 것이다.

 

 

3. Graham's Scan

---

`Graham Scan`은 정렬을 한 데이터를 읽어가면서, 해당 점에서 얻을 수 있는 가장 외곽의 점을 선택하는 방식이다.

 만약 다음 점을 선택하던 중에, 기존보다 외각점을 발견하게 된다면 현재 점을 빼고 찾은 점을 Convex Hull에 포함시킨다.   아래의 코드를 보자.

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
struct pt {
	int x, y;
	pt(int x = 0, int y = 0) :x(x), y(y){}
};
vector<pt> pts;
int v;
lld crs(pt a, pt b){
	return (lld)a.x*b.y - (lld)a.y*b.x;
}
int ccw(pt a, pt b, pt c){
	lld val = crs(pt(b.x - a.x, b.y - a.y), pt(c.x - a.x, c.y - a.y));
	if (val > 0) return 1;
	if (val < 0) return -1;
	return 0;
}
bool cmp(const pt& a, const pt& b){
	int val = ccw(pts[0], a, b);
	if (val > 0) return true;
	if (val < 0) return false;
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

vector<pt> gscan(){
	vector<pt> stk;
	for (int i = 0; i < pts.size(); i++){
		while (stk.size() >= 2 && ccw(stk[stk.size() - 2], stk.back(), pts[i]) <= 0){
			stk.pop_back();
		}
		stk.push_back(pts[i]);
	}
	return stk;
}

int main(){
	scanf("%d", &v);
	int lob = 0, a, b;
	pts.clear();
	for (int i = 0; i < v; i++){
		scanf("%d%d", &a, &b);
		pts.push_back(pt(a, b));
		if (pts[lob].x > pts[i].x || pts[lob].x == pts[i].x && pts[lob].y > pts[i].y) lob = i;
	}
	swap(pts[lob], pts[0]);
	sort(pts.begin()+1, pts.end(), cmp);
	vector<pt> con = gscan();
}

 이 코드에서는 입력을 받을때, 가장 아래쪽인 점을 하나 찾는다.

이 점은 결국 Convex Hull에 포함될 것이기 때문인데, 초기값 pts[0]에는 이 점을 포함시킨다. 그런 다음 정렬을 하게 되는데, 모든 정렬은 가장 아랫쪽인 점을 기준으로 CCW를 한 결과를 이용한다.

마지막으로 gscan이라는 함수를 호출하여, 그라함 스캔을 수행한다.