단순 다각형의 Convex Hull(convex hull of a simple polygon)

평면 위의 점집합에 대한 convex hull을 구하는 대표적인 알고리즘인 Graham scan에서는 먼저 기준점 하나를 선택한 뒤, 나머지 점들을 그 기준점에 대한 polar angle 순으로 정렬하는 과정이 필요하다. 그렇다면 점들이 이미 순차적으로 연결되어 simple polygon을 이루고 있다면, 별도의 정렬 과정 없이 Graham scan 알고리즘을 그대로 적용할 수 있을까?

이에 대한 답은 아니다. 간단한 반례를 통해 simple polygon의 꼭짓점 순서만으로는 Graham scan을 올바르게 수행할 수 없음을 확인할 수 있다. 그렇다면 simple polygon에 대해서도 항상 각도 정렬이 필요한 것일까?

이 질문에 대한 답 역시 아니다. simple polygon에서는 꼭짓점들이 이미 경계를 따라 순서대로 주어져 있다는 사실을 이용하면, 각도 정렬을 수행하지 않고도 convex hull을 효율적으로 구할 수 있는 알고리즘이 존재한다. 이제 이러한 성질을 이용하여 정렬 과정 없이 simple polygon의 convex hull을 구하는 알고리즘을 살펴보자.

Melkman Algorithm

먼저 폴리곤의 연속된 세 꼭짓점을 선택하여 반시계 방향의 삼각형을 만든다. 이 삼각형이 초기 convex hull이 되며, 꼭짓점들을 deque에 시작점이 양쪽 끝에 중복되도록 저장한다(bottom = top).

이후 폴리곤의 나머지 꼭짓점들을 순서대로 처리한다. 새 점이 현재 convex hull의 내부에 있으면 아무런 작업도 하지 않고 다음 점으로 넘어간다. 반면, 새 점이 convex hull의 외부에 있으면 deque의 양쪽 끝을 갱신하여 새 점이 포함되도록 convex hull을 수정한다.

먼저 bottom 쪽에서는 Graham scan의 scanning 과정과 동일하게 반시계 방향의 convexity가 만족될 때까지 꼭짓점을 제거한다. 다음으로 top 쪽에서는 시계 방향의 convexity가 만족될 때까지 꼭짓점을 제거한다. 양쪽 끝의 갱신이 완료되면 새 점을 deque의 양쪽 끝에 삽입하여 새로운 convex hull을 만든다.

이 과정을 모든 꼭짓점에 대해 반복하면 최종적인 convex hull을 얻을 수 있다. 각 꼭짓점은 deque에 한 번 삽입되고 최대 한 번 제거되므로 전체 알고리즘의 시간 복잡도는 \(O(N)\)이다.

int LEFTSIDE(CPoint A, CPoint B, CPoint C){ // cross(AB, AC) > 0: C가 AB 대해서 왼쪽
	return ((B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)) > 0;
}
std::vector<CPoint> convexhull_spolygon(std::vector<CPoint>& pts) {
    int N = pts.size();
    if (N < 3) return std::vector<CPoint> (); //null_vector;
    std::vector<CPoint> Q(2*N + 1);  // deque;
    int bot = N - 2, top = bot + 3;
    // |0|1|......|N-2|N-1|N+0|N+1|N+2|..............|2N|;
    //              bot    top    
    Q[bot] = Q[top] = pts[2];
    if (LEFTSIDE(pts[0], pts[1], pts[2])) { //2->0->1->2; Q에 ccw로 입력;
        Q[bot + 1] = pts[0]; Q[bot + 2] = pts[1];
    } else {
        Q[bot + 1] = pts[1]; Q[bot + 2] = pts[0];
    }
    int i = 2; // last touched index;
    while (++i < N) {
        // 기존의 convex_hull에 들어있으면 제외.
        if (LEFTSIDE(Q[bot + 0], Q[bot + 1], pts[i]) && 
            LEFTSIDE(Q[top - 1], Q[top + 0], pts[i]))
            continue;
        // bottom에 대해서 ccw 방향으로 체크(bot 증가 방향)
        // pts[i]가 (bot)->(bot+1)라인의 오른쪽에 있으면, 기존의 bottom을 제외;
        while (!LEFTSIDE(Q[bot], Q[bot + 1], pts[i]) && (bot < top)) bot++;
        Q[--bot] = pts[i];
        // 추가점에서 top->top-1의 ccw 방향으로 convexity 체크하여 만족하지 않은 경우
        // top을 감소
        while (!LEFTSIDE(Q[top - 1], Q[top], pts[i]) && (top > bot)) top-- ;
        Q[++top] = pts[i];
    }
    if (bot > 0) 
        for (int i = 0; i < (top-bot); ++i) Q[i] = Q[i + bot];
    Q.resize(top - bot); // Q[top] = Q[bot]
    return Q;
};