Convex Hull (Monotone Chain 기법) 연구 일지

https://www.geeksforgeeks.org/convex-hull-monotone-chain-algorithm/

Convex Hull | Monotone chain algorithm - GeeksforGeeks

Monotone Chain 기법에 관해 한글로 되어있는 자료들은 이해가 가지 않아서 GeeksforGeeks에서 공부 중입니다.

(최종 정리 내용은 22.04.21 연구이니 이를 참조해주시길 바랍니다.)

---

22.04.17 연구

현재까지 알아낸 것들을 정리하자면

 

동작원리

1. x축을 기준으로 하여 x좌표가 작은 순서대로 정렬한다. (x좌표가 같은 경우, y좌표가 작은 순서대로)

2. 제일 작은 x좌표로부터 Upper Hill과 Lower Hill을 나누어 Convex Hull을 구한다.

-

구조체 operator 선언 관련하여 구조체나 클래스에 대해 공부하면 다른 코드들까지의 습득력이 빠르고,

Object-Oriented Programming에 더 다가갈 수 있을 거 같습니다.

-

Time Complexity: O(n*log(n))

point들을 정렬하는 데에 의존하여 시간 복잡도가 저렇게 나옵니다.

하지만, Upper Hill과 Lower Hill은 O(n)으로 끝납니다.

 

(BOJ 1708을 Monotone Chain으로 구현한 코드입니다.)

저의 나름대로 해석하여 연구 중입니다.

// Monotone chain 기법 convex hull로 해보기
// O(nlogn) (정렬에 의해서)
// upper hulls, and lower hulls in O(n)

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define ll long long
using namespace std;

struct Point{
    ll x, y;
    
    // 구조체 operator 선언 공부하기
    bool operator <(const Point &p) const{
        return x < p.x || (x == p.x && y < p.y);
    }
    // 구조체 operator 잘 공부하면 아래와 같은 정렬
    // cmp 함수를 짤 일이 없을 거 같다.
    
    /*
    bool cmp(Point a, Point b){
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
    */
};

int n;
vector<Point> points;

/*
// GeeksforGeeks에서 가져온 내용
// 함수를 뜯어보니 CCW와 같아서 CCW를 구현해주었다.

// Cross product of two vectors OA and OB
// returns positive for counter clockwise
// turn and negative for clockwise turn
llu cross_product(Point O, Point A, Point B)
{
    return (A.x - O.x) * (B.y - O.y)
           - (A.y - O.y) * (B.x - O.x);
}
*/

ll ccw(Point a, Point b, Point c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

vector<Point> convexHull(){
    int size = points.size(), k = 0;
    
    if(size <= 3) return points;
    
    vector<Point> ans(2 * size);
    
    // Sort points lexicographically
    sort(points.begin(), points.end());
    
    // Build Lower Hull
    for(int i = 0; i < size; i++){
        while(k >= 2 && ccw(ans[k - 2], ans[k - 1], points[i]) <= 0){
            k--;
        }
        ans[k++] = points[i];
    }
    
    // Build Upper Hull
    for(int i = size - 1, t = k + 1; i > 0; i--){
        while(k >= t && ccw(ans[k - 2], ans[k - 1], points[i - 1]) <= 0){
            k--;
        }
        ans[k++] = points[i - 1];
    }
    
    ans.resize(k - 1);
    return ans;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        ll a, b; cin >> a >> b;
        points.push_back({a, b});
    }
    
    vector<Point> polygon = convexHull();
    
    cout << polygon.size();
    
    return 0;
}

---

22.04.21 추가 연구

여러 구글링을 하면서 더 편하게 구현하는 법과 동작원리를 더 디테일하게 설명하겠습니다.

 

[동작 원리]

1. x좌표를 기준으로 정렬합니다. (x좌표가 같은 경우 y좌표가 작은 순으로 정렬합니다.)

2. upperHull과 lowerHull로 나누어 구합니다. (Graham Scan과 다른 점입니다. 다른 점은 정렬 또한 마찬가지입니다.)

    2.1 upperHull 구하기

        정렬되어있는 점들을 차례로 CCW 하여 처음부터 시계방향으로 X좌표의 끝까지 담아냅니다.

    2.2 lowerHull 구하기

        reverse를 사용하여 x좌표 오른쪽에서 시작하도록 하기(구현에서 이 부분으로 인해 간단해졌습니다.)

        정렬되어있는 점들을 차례로 CCW 하여 처음부터 시계방향으로 X좌표의 시작까지 담아냅니다.

3. upperHull의 끝에는 lowerHull의 시작점, lowerHull의 끝에는 upperHull의 시작점이 담겨있으므로 이를 각각 pop 시킵니다.

 

[스스로 작성한 코드]

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

struct Point{
    ll x, y;
    
    bool operator <(const Point &p) const{
        return x < p.x || (x == p.x && y < p.y);
    }
};

int n;
vector<Point> points;

ll ccw(Point a, Point b, Point c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

// 느끼는 이점: 구현이 더 편한 거 같다?
pair<vector<Point>, vector<Point>> convexHull(){
    //if(points.size() <= 3) return points; return형 달라서 주석처리 함
    //나중에 구현해서 써먹을 때는 return 형 vector<Point>로 주기
    
    sort(points.begin(), points.end());
    
    // build upper hull
    vector<Point> uh;
    int un = 0;
    for(int i = 0; i < points.size(); i++){
        while(un >= 2 && ccw(uh[un - 2], uh[un - 1], points[i]) >= 0){
            uh.pop_back(); --un;
        }
        uh.push_back(points[i]); ++un;
    }
    uh.pop_back();
    //
    
    // reverse 함수를 사용해서 똑같이 반복하는 게 더 편함
    reverse(points.begin(), points.end());
    
    // build lower hull
    vector<Point> dh;
    int dn = 0;
    for(int i = 0; i < points.size(); i++){
        while(dn >= 2 && ccw(dh[dn - 2], dh[dn - 1], points[i]) >= 0){
            dh.pop_back(); --dn;
        }
        dh.push_back(points[i]); ++dn;
    }
    dh.pop_back();
    
    return {uh, dh};
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        ll a, b; cin >> a >> b;
        points.push_back({a, b});
    }
    
    pair<vector<Point>, vector<Point>> polygon = convexHull();
    
    vector<Point> upperHull = polygon.first;
    vector<Point> lowerHull = polygon.second;
    
    cout << upperHull.size() + lowerHull.size();
    
    /*
    for(int i = 0; i < upperHull.size(); i++){
        cout << upperHull[i].x << ' ' << upperHull[i].y << '\n';
    }
    
    for(int i = 0; i < lowerHull.size(); i++){
        cout << lowerHull[i].x << ' ' << lowerHull[i].y << '\n';
    }
    */
    
    return 0;
}

---

결론

백준에서 풀리지 않는 문제를 가지고서 구글링 하다가 대부분의 포스팅에서 Monotone Chain기법으로 풀어져있어서 공부하게 되었으나 Monotone Chain이 답이 될 수가 있다고는 공부를 하면서 못 느꼈습니다.

 

이러한 방법이 있다는 정도만 느낄 수 있었습니다.

다른 점은 Graham Scan은 시작점에서 반시계 혹은 시계 방향으로 크게 한 바퀴를 돌아 convex hull을 구하는 방식이고,

Monotone Chain은 2개의 Hull로 구한다는 그 차이점뿐이었던 것 같습니다.

 

구현도 크게 차이점은 없으나 PS를 할 때, 특정한 상황을 고려하여 기법을 선택할 수 있을 거 같습니다.

 

그래도 모르는 것보다는 아는 게 좋으니 만족하는 연구였습니다.