이 튜토리얼에서는 분할 정복(Divide and Conquer) 기법을 활용해 주어진 점 집합의 볼록 껍질(Convex Hull)을 구하는 C++ 프로그램을 살펴봅니다.
볼록 껍질이란?
볼록 껍질은 주어진 모든 점을 경계선 위 또는 내부에 포함하는 가장 작은 볼록 다각형을 의미합니다. 마치 고무줄을 모든 못에 걸어 팽팽하게 당겼을 때 만들어지는 형태라고 생각하면 쉽게 이해할 수 있습니다.
알고리즘 개요
이 프로그램은 전체 점 집합을 작은 그룹으로 반복적으로 나누고(분할), 각 그룹에 대해 브루트 포스 방식으로 부분 볼록 껍질을 계산한 뒤, 상단 및 하단 공통 접선을 찾아 두 볼록 껍질을 하나로 합치는(병합) 방식으로 동작합니다.
주요 단계는 다음과 같습니다.
- 점의 개수가 5개 이하가 되면 브루트 포스로 직접 볼록 껍질을 계산합니다.
- 그렇지 않으면 점들을 좌우 절반으로 나누어 각각 재귀적으로 볼록 껍질을 구합니다.
- 두 볼록 껍질 사이의 상단 접선(upper tangent)과 하단 접선(lower tangent)을 찾습니다.
- 접선을 기준으로 두 볼록 껍질을 병합하여 최종 결과를 얻습니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
// 다각형의 중심점 저장
pair<int, int> mid;
// 특정 점이 속한 사분면 계산
int quad(pair<int, int> p){
if (p.first >= 0 && p.second >= 0)
return 1;
if (p.first <= 0 && p.second >= 0)
return 2;
if (p.first <= 0 && p.second <= 0)
return 3;
return 4;
}
// 선분이 다각형에 닿는 방향 판별
int calc_line(pair<int, int> a, pair<int, int> b,
pair<int, int> c){
int res = (b.second-a.second)*(c.first-b.first) -
(c.second-b.second)*(b.first-a.first);
if (res == 0)
return 0;
if (res > 0)
return 1;
return -1;
}
// 정렬용 비교 함수
bool compare(pair<int, int> p1, pair<int, int> q1){
pair<int, int> p = make_pair(p1.first - mid.first,
p1.second - mid.second);
pair<int, int> q = make_pair(q1.first - mid.first,
q1.second - mid.second);
int one = quad(p);
int two = quad(q);
if (one != two)
return (one < two);
return (p.second*q.first < q.second*p.first);
}
// 두 볼록 껍질의 상단/하단 접선을 찾아 병합
vector<pair<int, int>> merger(vector<pair<int, int> > a,
vector<pair<int, int> > b){
int n1 = a.size(), n2 = b.size();
int ia = 0, ib = 0;
// a의 가장 오른쪽 점 찾기
for (int i=1; i<n1; i++)
if (a[i].first > a[ia].first)
ia = i;
// b의 가장 왼쪽 점 찾기
for (int i=1; i<n2; i++)
if (b[i].first < b[ib].first)
ib=i;
int inda = ia, indb = ib;
bool done = 0;
// 상단 접선 계산
while (!done){
done = 1;
while (calc_line(b[indb], a[inda], a[(inda+1)%n1]) >=0)
inda = (inda + 1) % n1;
while (calc_line(a[inda], b[indb], b[(n2+indb-1)%n2]) <=0){
indb = (n2+indb-1)%n2;
done = 0;
}
}
int uppera = inda, upperb = indb;
inda = ia, indb=ib;
done = 0;
// 하단 접선 계산
while (!done){
done = 1;
while (calc_line(a[inda], b[indb], b[(indb+1)%n2])>=0)
indb=(indb+1)%n2;
while (calc_line(b[indb], a[inda], a[(n1+inda-1)%n1])<=0){
inda=(n1+inda-1)%n1;
done=0;
}
}
int lowera = inda, lowerb = indb;
vector<pair<int, int>> ret;
// 두 다각형을 병합하여 볼록 껍질 생성
int ind = uppera;
ret.push_back(a[uppera]);
while (ind != lowera){
ind = (ind+1)%n1;
ret.push_back(a[ind]);
}
ind = lowerb;
ret.push_back(b[lowerb]);
while (ind != upperb){
ind = (ind+1)%n2;
ret.push_back(b[ind]);
}
return ret;
}
// 브루트 포스로 볼록 껍질 찾기
vector<pair<int, int>> bruteHull(vector<pair<int, int>> a){
set<pair<int, int> >s;
for (int i=0; i<a.size(); i++){
for (int j=i+1; j<a.size(); j++){
int x1 = a[i].first, x2 = a[j].first;
int y1 = a[i].second, y2 = a[j].second;
int a1 = y1-y2;
int b1 = x2-x1;
int c1 = x1*y2-y1*x2;
int pos = 0, neg = 0;
for (int k=0; k<a.size(); k++){
if (a1*a[k].first+b1*a[k].second+c1 <= 0)
neg++;
if (a1*a[k].first+b1*a[k].second+c1 >= 0)
pos++;
}
// 모든 점이 한 직선의 같은 쪽에 있으면 해당 두 점은 볼록 껍질의 변
if (pos == a.size() || neg == a.size()){
s.insert(a[i]);
s.insert(a[j]);
}
}
}
vector<pair<int, int>>ret;
for (auto e:s)
ret.push_back(e);
// 반시계 방향으로 정렬
mid = {0, 0};
int n = ret.size();
for (int i=0; i<n; i++){
mid.first += ret[i].first;
mid.second += ret[i].second;
ret[i].first *= n;
ret[i].second *= n;
}
sort(ret.begin(), ret.end(), compare);
for (int i=0; i<n; i++)
ret[i] = make_pair(ret[i].first/n, ret[i].second/n);
return ret;
}
// 볼록 껍질 값을 재귀적으로 반환
vector<pair<int, int>> divide(vector<pair<int, int>> a){
if (a.size() <= 5)
return bruteHull(a);
// left: 왼쪽 절반의 점들
// right: 오른쪽 절반의 점들
vector<pair<int, int>>left, right;
for (int i=0; i<a.size()/2; i++)
left.push_back(a[i]);
for (int i=a.size()/2; i<a.size(); i++)
right.push_back(a[i]);
vector<pair<int, int>>left_hull = divide(left);
vector<pair<int, int>>right_hull = divide(right);
// 두 볼록 껍질 병합
return merger(left_hull, right_hull);
}
int main(){
vector<pair<int, int> > a;
a.push_back(make_pair(0, 0));
a.push_back(make_pair(1, -4));
a.push_back(make_pair(-1, -5));
a.push_back(make_pair(-5, -3));
a.push_back(make_pair(-3, -1));
a.push_back(make_pair(-1, -3));
a.push_back(make_pair(-2, -2));
a.push_back(make_pair(-1, -1));
a.push_back(make_pair(-2, -1));
a.push_back(make_pair(-1, 1));
int n = a.size();
sort(a.begin(), a.end());
vector<pair<int, int> >ans = divide(a);
cout << "Convex Hull:\n";
for (auto e:ans)
cout << e.first << " "<< e.second << endl;
return 0;
}실행 결과
Convex Hull: -5 -3 -1 -5 1 -4 0 0 -1 1
정리
분할 정복 기반 볼록 껍질 알고리즘은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 브루트 포스 방식(O(n³))보다 훨씬 효율적입니다. 점이 많아질수록 분할 정복 방식의 성능상 이점이 더욱 커지므로, 대량의 좌표 데이터를 다루는 컴퓨터 그래픽스, 지리 정보 시스템(GIS), 충돌 감지 등의 분야에서 널리 활용됩니다.