컨벡스 헐 알고리즘

Convex Hull 알고리즘은 말 그대로 볼록한 껍질을 만드는 알고리즘입니다.

 

이번 포스팅에서는 2차원에 대해서만 다룰 것이기 때문에 볼록 다각형만을 다룰 것입니다.

컨벡스 헐 알고리즘을 통해 볼록 다각형을 구성하는 꼭짓점을 얻을 수 있습니다.

---

먼저 점들의 좌표를 입력받아 배열에 담습니다.

점들 중에서 y좌표가 가장 작은 것을 배열의 맨 앞으로 가져와 기준점 (1번)으로 둡니다.

그중에서 y좌표가 동일한 것이 있다면 x좌표가 가장 작은 것을 기준점으로 삼습니다.

 

그 후, 기준점과 +x축으로부터 반시계 방향으로 각도가 작은 것부터 큰 순서대로 정렬합니다.(2번 ~ 10번)

그중에서 각도가 동일한 것이 있다면 기준점과 거리가 가까운 것이 앞으로 오도록 정렬합니다.

 

(문제에 따라서 기준 좌표와 정렬 방향을 달리 해야 할 수도 있습니다.)

 

정렬이 마무리 되었다면 1번과 2번을 순서대로 스택에 넣습니다.

2번과 1번을 스택에서 꺼내고 3번과 비교하여 좌회전을 한다면 1번과 2번을 스택에 다시 넣습니다.

추가로 좌회전이 가능했던 3번도 스택에 넣습니다.

 

소스코드에서 보겠지만 미리 말씀드리면, 좌회전인지 판단하는 함수를 CCW(counter-clockwise)라고 합니다.

 

3번과 2번을 스택에서 꺼내고 4번과 비교하여 좌회전을 한다면 2번과 3번을 스택에 다시 넣습니다.

추가로 좌회전이 가능했던 4번도 스택에 넣습니다.

 

4번과 3번을 스택에서 꺼내고 5번과 비교하여 좌회전을 한다면 3번과 4번을 스택에 다시 넣습니다.

추가로 좌회전이 가능했던 5번도 스택에 넣습니다.

5번과 4번을 스택에서 꺼내고 6번과 비교했을 때 우회전을 하게 되어 오목한 모양이 생깁니다.

첫 번째로 꺼냈던 5번은 스택에 넣지 않고 두 번째로 꺼냈던 4번만 스택에 도로 집어넣습니다.

우회전을 했기 때문에 6번을 스택에 넣지 않습니다.

4번과 3번을 스택에서 꺼내고 6번과 비교하여 좌회전을 한다면 3번과 4번을 스택에 다시 넣습니다.

추가로 좌회전이 가능했던 6번도 스택에 넣습니다.

6번과 4번을 스택에서 꺼내고 7번과 비교하여 좌회전을 한다면 4번과 6번을 스택에 다시 넣습니다.

추가로 좌회전이 가능했던 7번도 스택에 넣습니다.

 

6번과 7번을 스택에서 꺼내고 8번과 비교했을 때 우회전을 하게 되어 오목한 모양이 생깁니다.

첫 번째로 꺼냈던 7번은 스택에 넣지 않고 두 번째로 꺼냈던 6번만 스택에 도로 집어넣습니다.

우회전을 했기 때문에 8번을 스택에 넣지 않습니다.

4번과 6번을 스택에서 꺼내고 8번과 비교했을 때 일직선이 됩니다.

첫 번째로 꺼냈던 6번은 스택에 넣지 않고 두 번째로 꺼냈던 4번만 스택에 도로 집어넣습니다.

일직선이 됐기 때문에 8번을 스택에 넣지 않습니다.

4번과 3번을 스택에서 꺼내고 8번과 비교하여 좌회전을 한다면 3번과 4번을 스택에 다시 넣습니다.

추가로 좌회전이 가능했던 8번도 스택에 넣습니다.

8번과 4번을 스택에서 꺼내고 9번과 비교하여 좌회전을 한다면 4번과 8번을 스택에 다시 넣습니다.

추가로 좌회전이 가능했던 9번도 스택에 넣습니다.

9번과 8번을 스택에서 꺼내고 10번과 비교하여 좌회전을 한다면 8번과 9번을 스택에 다시 넣습니다.

추가로 좌회전이 가능했던 10번도 스택에 넣습니다.

볼록 다각형을 구성하는 꼭짓점을 전부 찾아내는 데 성공했습니다.

 

이를 소스코드로 구현해보겠습니다.

---

struct dot {
	ll x, y; //입력받을 좌표를 구조체로 구성합니다.
};

vector<dot> dots; //받은 좌표를 벡터에 저장할 것입니다.

int ccw(dot A, dot B, dot C) { //좌회전인지 판단할 함수
	ll rot = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
    //직선 AB와 AC의 외적결과
    
	if (rot > 0) return 1;       //0보다 크면 좌회전
	else if (rot < 0) return -1; //0보다 작으면 우회전
	else return 0;               //0이면 직선
}

ll dist(dot a, dot b) {
	return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
    //두 점사이의 거리의 제곱. 대소 관계를 나타내기 위함이라 루트를 씌우지 않아도 됩니다.
}

bool cmp(const dot& a, const dot& b) { //주어진 점을 정렬할 방법
	int val = ccw(dots[0], a, b); 
	if (val > 0) return true;  
	if (val < 0) return false; 
    //좌회전을 하는 순서대로 바꿈
    
	if (dist(dots[0], a) < dist(dots[0], b)) return true;
	return false;
    //직진이라면 기준점과의 거리가 짧은 순서대로 바꿈
}

vector<dot> graham() {
	vector<dot> s; //꼭지점을 담을 벡터
	for (int i = 0; i < dots.size(); i++) {//정렬된 점을 차례대로 탐색
		while (2 <= s.size() && ccw(s[s.size() - 2], s[s.size() - 1], dots[i]) <= 0)
			s.pop_back();
            //좌회전하지 않으면 스택의 가장 상위 점을 뽑아냅니다.
		s.push_back(dots[i]);
        //점이 2개 미만이면 ccw 비교가 안되므로 점을 추가합니다.
        //좌회전을 한다면 스택에 해당 점을 추가합니다.
	}
	return s;
    //꼭지점을 모은 벡터를 반환
}

void convexhull() {
	int temp = 0;
	for (int i = 1;i < dots.size();i++)
		if (dots[i].y < dots[temp].y || (dots[i].y == dots[temp].y && dots[i].x < dots[temp].x))
			temp = i;
            //기준점이 될 점을 골라냅니다.
	swap(dots[temp], dots[0]); //기준점이 될 점을 맨 앞으로 이동시킵니다.
	sort(dots.begin() + 1, dots.end(), cmp);//기준점을 제외한 점을 정렬시킵니다.
	vector<dot> res = graham();//그라함 스캔으로 볼록 다각형의 꼭지점을 찾아봅니다.
	cout << res.size();
}

---

컨벡스 헐 알고리즘의 시간 복잡도

 

주어진 점을 반시계 방향으로 정렬하는데 O(NlogN)만큼의 시간이 소요됩니다.

스택을 이용하여 볼록 다각형의 껍질을 찾으려 할 때 꼭짓점의 개수만큼 탐색을 하여 O(N)의 시간이 소요됩니다.

따라서 컨벡스 헐 알고리즘의 시간복잡도는 max(O(NlogN), O(N)) = O(NlogN)입니다.

---

연습문제

 

2020/10/24 - [백준] - 백준 소스코드 [C++] 1708 볼록 껍질

2020/10/24 - [백준] - 백준 소스코드 [C++] 2699 격자점 컨벡스 헐

 

컨벡스 헐 알고리즘에 대한 포스팅이었습니다.

오타 지적과 조언은 언제나 환영입니다.