컨벡스 헐 (Convex Hull) 알고리즘
주어진 점들을 모두 감싸는 가장 작은 볼록 다각형을 구하는 그레이엄 스캔과 모노톤 체인 알고리즘을 정리했습니다.
개요
컨벡스 헐(Convex Hull, 볼록 껍질) 알고리즘은 2차원 평면에 여러 개의 점이 주어졌을 때, 그 점들을 모두 포함하는 가장 작은 볼록 다각형을 만드는 알고리즘이다.
볼록 다각형은 다각형 내부의 임의의 두 점을 연결하는 선분이 항상 다각형 내부에 존재하는 모양이다. 즉, 내각이 모두 180도 미만이다.
컨벡스 헐의 꼭짓점이 되는 점들은 주어진 점들 중 가장 바깥쪽에 위치한 점들이다.
CCW
컨벡스 헐을 구현할 때 CCW를 사용한다. 세 점의 방향 관계를 파악하는 알고리즘으로 새로운 점(세번째 점)을 추가할 때 이 점이 왼쪽으로 꺾이는지(좌회전), 오른쪽으로 꺾이는지(우회전)을 판단할 수 있다.
CCW에 자세한 내용은 위 링크를 참고하자.
그레이엄 스캔 (Graham Scan)
그레이엄 스캔은 기준점을 잡고 각도로 정렬하여 한 바퀴 도는 방식의 알고리즘이다.
- y 좌표가 가장 낮은 기준 점 A를 찾는다. 점 A는 반드시 컨벡스 헐에 포함된다.
- CCW를 사용하여 다른 점들을 각도에 따라 정렬한다.
- 반시계 방향으로 각에 따라 점들을 접근하면서 선으로 이어준다.
- 세 점들을 이어 나가면서 우회전이 일어나지 않는 점들만 넣어준다.
- 우회전이 일어난다면 볼록 다각형이 아니다.
정렬하는데 O(N log N)이 걸리고, n-1개의 점들을 점검하는데 O(N)이 걸리므로 전체적으로 O(N log N)의 시간 복잡도를 가진다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <algorithm>
#include <iostream>
#include <vector>
struct Point
{
long long x, y;
};
Point p0; // 기준점
long long distSq(const Point& p1, const Point& p2)
{
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
long long ccw(const Point& a, const Point& b, const Point& c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool compare(const Point& p1, const Point& p2)
{
long long order = ccw(p0, p1, p2);
// 각도가 같다면, 기준점과의 거리가 더 가까운 순으로 정렬
if (order == 0)
{
return distSq(p0, p1) < distSq(p0, p2);
}
return order > 0;
}
std::vector<Point> grahamScan(std::vector<Point>& points)
{
const int n = static_cast<int>(points.size());
if (n < 3)
{
return points;
}
// 1. 기준점 찾기
int minIndex = 0;
for (int i = 1; i < n; i++)
{
if (points[i].y < points[minIndex].y ||
(points[i].y == points[minIndex].y && points[i].x < points[minIndex].x))
{
minIndex = i;
}
}
std::swap(points[0], points[minIndex]);
p0 = points[0];
// 2. 반시계 방향 정렬
std::sort(points.begin() + 1, points.end(), compare);
// 3. hull을 이루는 점 탐색
std::vector<Point> hull;
hull.push_back(points[0]);
hull.push_back(points[1]);
hull.push_back(points[2]);
for (int i = 3; i < n; i++)
{
while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), points[i]) <= 0)
{
hull.pop_back();
}
hull.push_back(points[i]);
}
return hull;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::vector<Point> input = { {0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3} };
const std::vector<Point> result = grahamScan(input);
// Output : (0,0), (3,1), (4,4), (0,3)
for (const auto& elem : result)
{
std::cout << '(' << elem.x << ',' << elem.y << ')' << '\n';
}
return 0;
}
위 예제 입력에 대한 이미지이니 참고하자!
각도를 비교하는 compare 함수에서 CCW == 0인 경우, 일직선 상에 놓인 것이므로 기준점과의 거리를 비교하여 가까운 순으로 정렬한다.
모노톤 체인(Monotone Chain)
앤드류의 알고리즘이라고도 알려져 있는 모노톤 체인은 2차원 평면의 점들을 x 좌표 혹은 y 좌표 기준으로 정렬한 뒤, 컨벡스 헐의 윗껍질과 아랫껍질을 각각 구하여 완성하는 알고리즘이다.
그레이엄 스캔처럼 각도 정렬이 필요 없어 구현이 더 직관적이고 쉽다고 생각한다.
x축 정렬을 기준으로 이야기해 보자.
- 모든 점을 x 좌표가 작은 순, 같다면 y 좌표가 작은 순으로 오름차순 정렬한다.
- 아랫껍질(Lower Hull)을 생성한다. 세 점들을 이어나가면서 좌회전 하는 점들만 넣어준다.
- 마찬가지로 윗껍질(Upper Hull)을 생성한다.
- 아랫껍질과 윗껍질을 합치면서 중복되는 점(양 끝점)을 제거하면 전체 컨벡스 헐이 완성된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <algorithm>
#include <iostream>
#include <vector>
struct Point
{
long long x, y;
bool operator<(const Point& other) const
{
if (x != other.x)
{
return x < other.x;
}
return y < other.y;
}
};
long long ccw(const Point& a, const Point& b, const Point& c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
std::vector<Point> monotoneChain(std::vector<Point>& points)
{
const int n = static_cast<int>(points.size());
if (n < 3)
{
return points;
}
std::sort(points.begin(), points.end());
std::vector<Point> lower_hull;
std::vector<Point> upper_hull;
for (int i = 0; i < n; i++)
{
while (lower_hull.size() >= 2 && ccw(lower_hull[lower_hull.size() - 2], lower_hull.back(), points[i]) <= 0)
{
lower_hull.pop_back();
}
lower_hull.push_back(points[i]);
}
for (int i = n - 1; i >= 0; i--)
{
while (upper_hull.size() >= 2 && ccw(upper_hull[upper_hull.size() - 2], upper_hull.back(), points[i]) <= 0)
{
upper_hull.pop_back();
}
upper_hull.push_back(points[i]);
}
lower_hull.insert(lower_hull.end(), upper_hull.begin() + 1, upper_hull.end() - 1);
return lower_hull;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::vector<Point> input = { {0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3} };
const std::vector<Point> result = monotoneChain(input);
// Output : (0,0), (3,1), (4,4), (0,3)
for (const auto& elem : result)
{
std::cout << '(' << elem.x << ',' << elem.y << ')' << '\n';
}
return 0;
}
중복 점 제거하는거만 신경쓰면, 구현이 더 직관적이라 개인적으로는 그레이엄 스캔보다 나은 듯하다.
문제 풀이
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIoKUq6rqUDFAWN
백준이 그립다. 컨벡스 헐 문제 찾기가 너무 어렵다…..
SW Expert Academy에서 한 문제 찾았으니 풀어보자…. 백준아 돌아와라
참고