볼록 껍질 구성¶
이 글에서는 점 집합으로부터 볼록 껍질을 구성하는 문제를 다룹니다.
평면 위에 $N$개의 점이 주어졌을 때, 볼록 껍질, 즉 주어진 모든 점을 포함하는 가장 작은 볼록 다각형을 생성하는 것이 목표입니다.
1972년 Graham이 발표한 그레이엄 스캔(Graham's scan) 알고리즘과 1979년 Andrew가 발표한 단조 체인(Monotone chain) 알고리즘을 살펴보겠습니다. 두 알고리즘 모두 $\mathcal{O}(N \log N)$이며, 병렬 처리나 온라인 처리가 관련된 일부 문제를 제외하면 점근적으로 최적입니다(점근적으로 더 나은 알고리즘이 존재하지 않음이 증명되어 있습니다).
그레이엄 스캔 알고리즘¶
이 알고리즘은 먼저 가장 아래쪽에 있는 점 $P_0$을 찾습니다. Y 좌표가 같은 점이 여러 개라면 X 좌표가 더 작은 점을 택합니다. 이 단계는 $\mathcal{O}(N)$ 시간이 걸립니다.
다음으로, 나머지 모든 점을 시계 방향으로 편각에 따라 정렬합니다. 두 개 이상의 점의 편각이 같으면 $P_0$으로부터의 거리가 가까운 순서로 순서를 정해야 합니다.
그런 다음 각 점을 하나씩 순회하면서 현재 점과 그 이전의 두 점이 시계 방향 회전을 이루는지 확인하고, 그렇지 않으면 볼록하지 않은 모양이 되므로 이전 점을 버립니다. 시계 방향인지 반시계 방향인지는 방향(orientation)을 확인하여 판별할 수 있습니다.
점들을 저장하기 위해 스택을 사용하며, 원래의 점 $P_0$에 도달하면 알고리즘이 끝나고 볼록 껍질의 모든 점을 시계 방향 순서로 담은 스택을 반환합니다.
그레이엄 스캔을 수행하면서 공선(collinear) 점들도 포함해야 한다면 정렬 후에 한 단계가 더 필요합니다. 정렬된 벡터의 마지막 그룹, 즉 $P_0$ 및 마지막 점과 한 직선 위에 있는 점들을 구해야 합니다. 모든 공선 점을 출력할 수 있도록 이 반직선 위의 점들의 순서를 뒤집어야 하며, 그렇지 않으면 알고리즘은 이 직선에서 가장 가까운 점만 취하고 멈추게 됩니다. 이 단계는 공선 점을 포함하지 않는 버전의 알고리즘에는 넣지 않아야 하며, 그렇지 않으면 가장 작은 볼록 껍질을 얻을 수 없습니다.
구현¶
struct pt {
double x, y;
bool operator == (pt const& t) const {
return x == t.x && y == t.y;
}
};
int orientation(pt a, pt b, pt c) {
double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
if (v < 0) return -1; // clockwise
if (v > 0) return +1; // counter-clockwise
return 0;
}
bool cw(pt a, pt b, pt c, bool include_collinear) {
int o = orientation(a, b, c);
return o < 0 || (include_collinear && o == 0);
}
bool collinear(pt a, pt b, pt c) { return orientation(a, b, c) == 0; }
void convex_hull(vector<pt>& a, bool include_collinear = false) {
pt p0 = *min_element(a.begin(), a.end(), [](pt a, pt b) {
return make_pair(a.y, a.x) < make_pair(b.y, b.x);
});
sort(a.begin(), a.end(), [&p0](const pt& a, const pt& b) {
int o = orientation(p0, a, b);
if (o == 0)
return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y)
< (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
return o < 0;
});
if (include_collinear) {
int i = (int)a.size()-1;
while (i >= 0 && collinear(p0, a[i], a.back())) i--;
reverse(a.begin()+i+1, a.end());
}
vector<pt> st;
for (int i = 0; i < (int)a.size(); i++) {
while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear))
st.pop_back();
st.push_back(a[i]);
}
if (include_collinear == false && st.size() == 2 && st[0] == st[1])
st.pop_back();
a = st;
}
단조 체인 알고리즘¶
이 알고리즘은 먼저 가장 왼쪽 점 A와 가장 오른쪽 점 B를 찾습니다. 그러한 점이 여러 개 존재하는 경우, 왼쪽 점들 중 가장 낮은 점(Y 좌표가 가장 작은 점)을 A로, 오른쪽 점들 중 가장 높은 점(Y 좌표가 가장 큰 점)을 B로 택합니다. A보다 더 왼쪽에 있거나 B보다 더 오른쪽에 있는 점은 없으므로, A와 B는 분명히 둘 다 볼록 껍질에 속해야 합니다.
이제 AB를 지나는 직선을 그립니다. 이 직선은 나머지 모든 점을 두 집합 S1과 S2로 나누는데, S1은 A와 B를 잇는 직선보다 위에 있는 모든 점을 포함하고, S2는 A와 B를 잇는 직선보다 아래에 있는 모든 점을 포함합니다. A와 B를 잇는 직선 위에 있는 점들은 어느 집합에 속해도 됩니다. 점 A와 B는 두 집합 모두에 속합니다. 이제 알고리즘은 위쪽 집합 S1과 아래쪽 집합 S2를 구성한 다음, 이들을 합쳐 답을 얻습니다.
위쪽 집합을 구하기 위해 모든 점을 x좌표에 따라 정렬합니다. 각 점에 대해, 현재 점이 마지막 점(B로 정의한 점)인지, 또는 A와 현재 점을 잇는 직선과 현재 점과 B를 잇는 직선 사이의 방향이 시계 방향인지 확인합니다. 이러한 경우 현재 점은 위쪽 집합 S1에 속합니다. 시계 방향인지 반시계 방향인지는 방향(orientation)을 확인하여 판별할 수 있습니다.
주어진 점이 위쪽 집합에 속한다면, 위쪽 볼록 껍질에서 끝에서 두 번째 점과 마지막 점을 잇는 선이 위쪽 볼록 껍질의 마지막 점과 현재 점을 잇는 선과 이루는 각을 확인합니다. 이 각이 시계 방향이 아니라면, 위쪽 볼록 껍질에 가장 최근에 추가된 점을 제거합니다. 현재 점이 볼록 껍질에 추가되면 이전 점을 포함할 수 있게 되기 때문입니다.
아래쪽 집합 S2에도 같은 논리가 적용됩니다. 현재 점이 B이거나, A와 현재 점을 잇는 선과 현재 점과 B를 잇는 선의 방향이 반시계 방향이라면, 그 점은 S2에 속합니다.
주어진 점이 아래쪽 집합에 속한다면, 시계 방향 대신 반시계 방향인지를 확인한다는 점을 제외하고는 위쪽 집합의 점과 비슷하게 처리합니다. 따라서 아래쪽 볼록 껍질에서 끝에서 두 번째 점과 마지막 점을 잇는 선이 아래쪽 볼록 껍질의 마지막 점과 현재 점을 잇는 선과 이루는 각이 반시계 방향이 아니라면, 아래쪽 볼록 껍질에 가장 최근에 추가된 점을 제거합니다. 현재 점이 껍질에 추가되면 이전 점을 포함할 수 있게 되기 때문입니다.
최종 볼록 껍질은 위쪽 볼록 껍질과 아래쪽 볼록 껍질의 합집합으로 얻어지며 시계 방향 껍질을 이룹니다. 구현은 다음과 같습니다.
한 직선 위에 있는 점들도 포함해야 한다면, 시계 방향/반시계 방향 판정 루틴에서 그런 점들을 확인하기만 하면 됩니다. 그러나 이렇게 하면 입력된 모든 점이 한 직선 위에 놓이는 퇴화 경우가 생길 수 있으며, 이때 알고리즘은 중복된 점들을 출력하게 됩니다. 이를 해결하기 위해 위쪽 껍질이 모든 점을 포함하는지 확인하고, 그렇다면 점들을 역순으로 반환하기만 하면 됩니다. 이 경우 Graham의 구현이 반환하는 결과가 바로 그것이기 때문입니다.
구현¶
struct pt {
double x, y;
};
int orientation(pt a, pt b, pt c) {
double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
if (v < 0) return -1; // clockwise
if (v > 0) return +1; // counter-clockwise
return 0;
}
bool cw(pt a, pt b, pt c, bool include_collinear) {
int o = orientation(a, b, c);
return o < 0 || (include_collinear && o == 0);
}
bool ccw(pt a, pt b, pt c, bool include_collinear) {
int o = orientation(a, b, c);
return o > 0 || (include_collinear && o == 0);
}
void convex_hull(vector<pt>& a, bool include_collinear = false) {
if (a.size() == 1)
return;
sort(a.begin(), a.end(), [](pt a, pt b) {
return make_pair(a.x, a.y) < make_pair(b.x, b.y);
});
pt p1 = a[0], p2 = a.back();
vector<pt> up, down;
up.push_back(p1);
down.push_back(p1);
for (int i = 1; i < (int)a.size(); i++) {
if (i == a.size() - 1 || cw(p1, a[i], p2, include_collinear)) {
while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i], include_collinear))
up.pop_back();
up.push_back(a[i]);
}
if (i == a.size() - 1 || ccw(p1, a[i], p2, include_collinear)) {
while (down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i], include_collinear))
down.pop_back();
down.push_back(a[i]);
}
}
if (include_collinear && up.size() == a.size()) {
reverse(a.begin(), a.end());
return;
}
a.clear();
for (int i = 0; i < (int)up.size(); i++)
a.push_back(up[i]);
for (int i = down.size() - 2; i > 0; i--)
a.push_back(down[i]);
}