컨벡스 헐 (Convex Hull) 알고리즘

개요

---

컨벡스 헐(Convex Hull, 볼록 껍질) 알고리즘은 2차원 평면에 여러 개의 점이 주어졌을 때, 그 점들을 모두 포함하는 가장 작은 볼록 다각형을 만드는 알고리즘이다.

볼록 다각형은 다각형 내부의 임의의 두 점을 연결하는 선분이 항상 다각형 내부에 존재하는 모양이다. 즉, 내각이 모두 180도 미만이다.

컨벡스 헐의 꼭짓점이 되는 점들은 주어진 점들 중 가장 바깥쪽에 위치한 점들이다.

CCW

---

컨벡스 헐을 구현할 때 CCW를 사용한다. 세 점의 방향 관계를 파악하는 알고리즘으로 새로운 점(세번째 점)을 추가할 때 이 점이 왼쪽으로 꺾이는지(좌회전), 오른쪽으로 꺾이는지(우회전)을 판단할 수 있다.

CCW 포스팅

CCW에 자세한 내용은 위 링크를 참고하자.

그레이엄 스캔 (Graham Scan)

---

그레이엄 스캔은 기준점을 잡고 각도로 정렬하여 한 바퀴 도는 방식의 알고리즘이다.

1. y 좌표가 가장 낮은 기준 점 A를 찾는다. 점 A는 반드시 컨벡스 헐에 포함된다.
2. CCW를 사용하여 다른 점들을 각도에 따라 정렬한다.
3. 반시계 방향으로 각에 따라 점들을 접근하면서 선으로 이어준다.
4. 세 점들을 이어 나가면서 우회전이 일어나지 않는 점들만 넣어준다.
5. 우회전이 일어난다면 볼록 다각형이 아니다.

정렬하는데 O(N log N)이 걸리고, n-1개의 점들을 점검하는데 O(N)이 걸리므로 전체적으로 O(N log N)의 시간 복잡도를 가진다.

#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축 정렬을 기준으로 이야기해 보자.

1. 모든 점을 x 좌표가 작은 순, 같다면 y 좌표가 작은 순으로 오름차순 정렬한다.
2. 아랫껍질(Lower Hull)을 생성한다. 세 점들을 이어나가면서 좌회전 하는 점들만 넣어준다.
3. 마찬가지로 윗껍질(Upper Hull)을 생성한다.
4. 아랫껍질과 윗껍질을 합치면서 중복되는 점(양 끝점)을 제거하면 전체 컨벡스 헐이 완성된다.

#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에서 한 문제 찾았으니 풀어보자…. 백준아 돌아와라

참고

• https://velog.io/@frog_slayer/Algo-Graham-Scan
• https://www.desmos.com/calculator?lang=ko
• https://deepdata.tistory.com/992
• https://deepdata.tistory.com/992