Convex Hull과 CCW

* Convex Hull: 볼록 껍질

* CCW: counter clockwise, 시계 반대 방향

 

 

 

외적을 이용하는 기하학 문제에서 쓰인다.

주어진 점을 모두 포함하는 볼록 다각형의 꼭짓점을 찾아야 한다.

 

 

 

 

 

1. 볼록 껍질의 한 꼭짓점을 찾는다.

y좌표가 가장 크거나 가장 작은 점, x좌표가 가장 크거나 가장 작은 점 중 아무거나 고르면 된다.

해당 점을 모두 포함하는 MBR(Minimal Bounding Rectangle)과 볼록 껍질이 무조건 접해야하기 때문

이때는 간단한 비교 함수를 사용해 점을 정렬하고 첫 번째 원소를 기준점으로 잡는다.

 

 

2. 기준점을 기준으로 다른 점을 시계방향으로 정렬한다.

이때 외적이 쓰인다.

벡터 OA와 OB의 외적 < 0 ⇒ O를 기준으로 A, B가 시계방향으로 존재한다.

 

따라서 아래와 같은 비교함수를 사용한다.

OA와 OB가 평행하면 O에 더 가까운 점을 우선으로 정렬한다.

bool sort_clockwise(point A, point B) {
	//sort points clockwise based on p[0],
	//if parallel, nearer first
	long long a = A.dx * B.dy - A.dy * B.dx;
	if (a == 0) return A.dx * A.dx < B.dx * B.dx;
	else return a < 0;
}

 

 

3. 볼록 껍질을 찾는다.

볼록 껍질이라고 가정한 fir, sec와 새로운 점 p[i]를 이용해

sec가 볼록 껍질에 해당하는 점인지 판단하는 과정을 반복한다.

	v.push_back(p[0]), v.push_back(p[1]);
	for (int i = 2; i < N; ++i) {
		while (v.size() > 1) {
			point sec = v.back(); v.pop_back();
			point fir = v.back();
			if (!ccw(fir, sec, p[i])) { v.push_back(sec); break; }
			//sec이 적합한지 아닌지 판정
		}
		v.push_back(p[i]);
	}

 

• fir=p[3]  sec=p[4]  p[i]=p[5]
  p[3] 기준, p[4] p[5] 시계방향
• fir=p[4]  sec=p[5]  p[i]=p[6]
  p[4] 기준, p[5] p[6] 반시계방향 ⇒ p[5]를 삭제한다.
• fir=p[4]  sec=p[6]  pi[]=p[7]
  p[4] 기준, p[6] p[7] 일직선 상에 존재 => 경우에 따라 p[6]을 삭제한다.

한 변에 여러 개의 점이 존재하지 않는다는 가정이면 p[6]을 삭제해야 하고, 아닌 경우 삭제하지 않는다.

경우를 고려해 아래 ccw 함수의 비교 연산자를 수정한다.

사실 위의 sort_clockwise 비교 함수에서도 dx, dy 사용하지 않고 ccw함수 사용해도 될 듯... 그럼 일직선 상의 점을 찾기 어려우려나

 

bool ccw(point O, point A, point B) {
	// OA X OB < 0 => clockwise
	if ((A.x - O.x) * (B.y - O.y) >= (A.y - O.y)* (B.x - O.x)) return true;
	else return false;
}

 

p[i]=13일 땐 아래 과정을 통해 처리한다.

 

 

 

전체코드와 주절주절

 

point x,y=좌표 dx,dy=기준점에서의 벡터 성분

v  convex hull의 꼭짓점을 시계방향으로 저장하는 벡터

이 코드에서는 v에 컨벡스헐의 꼭짓점을

- y좌표, x좌표가 가장 큰 점을 시작으로

- 시계 방향으로

- 일직선 상의 점은 존재하지 않도록 저장한다.

조건에 따라 ccw의 비교연산자, 출력 순서를 수정하자.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct point {
	long long x, y, dx = 0, dy = 0;
};
point p[100000];
vector<point> v;
bool find_zero(point A, point B) {
	//point with max y, max x = starting point = p[0]
	if (A.y == B.y) return A.x > B.x;
	else return A.y > B.y;
}
bool sort_clockwise(point A, point B) {
	//sort points clockwise based on p[0],
	//if parallel, nearer first
	long long a = A.dx * B.dy - A.dy * B.dx;
	if (a == 0) return A.dx * A.dx < B.dx * B.dx;
	else return a < 0;
}
bool ccw(point O, point A, point B) {
	// OA X OB < 0 => clockwise
	if ((A.x - O.x) * (B.y - O.y) >= (A.y - O.y)* (B.x - O.x)) return true;
	else return false;
}
int main() {
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%lld%lld", &p[i].x, &p[i].y);

	// Sort points clockwise based on p[0](y max, x max)
	sort(p, p + N, find_zero);
	int x0 = p[0].x, y0 = p[0].y;
	for (int i = 1; i < N; ++i) p[i].dx = p[i].x - x0, p[i].dy = p[i].y - y0;
	sort(p + 1, p + N, sort_clockwise);

	// Find convex hull
	v.push_back(p[0]), v.push_back(p[1]);
	for (int i = 2; i < N; ++i) {
		while (v.size() > 1) {
			point sec = v.back(); v.pop_back();
			point fir = v.back();
			if (!ccw(fir, sec, p[i])) { v.push_back(sec); break; }
			//sec이 적합한지 아닌지 판정
		}
		v.push_back(p[i]);
	}
	
	printf("%d", v.size()); return 0;
}

 

대충 이런 건가보다,, 하고 넘겼다가 매번 헷갈렸다.

다시 이해하려고 그림을 매번 그리기엔 시간이 오래 걸리니 이제는 제대로 기억해야할 듯

 

 

 

Convex Hull 문제들

1708 볼록 껍질

2699 격자점 컨벡스헐

4181 Convex Hull

6850 Cows