그레이엄 알고리즘

그레이엄 알고리즘

그레이엄 알고리즘은 다음과 같은 관찰에 기반한 자비스 알고리즘의 최적화입니다. 모든 점을 점 $p_0$에 대한 극각을 기준으로 정렬하면, 볼록 껍질은 이렇게 정렬된 점 배열의 어떤 부분 수열이 됩니다.

알고리즘은 이 정렬된 배열의 각 접두사에 대한 볼록 껍질을 차례로 구성합니다. $i$번째 점을 껍질에 추가할 때는 새 껍질에 포함되지 않을 마지막으로 추가된 점 몇 개, 즉 새 점과 그 이전 점에 의해 「덮이는」 점들만 제거하면 된다는 것을 알 수 있습니다.

이 삭제를 효율적으로 수행하기 위해, 볼록 껍질을 스택에 저장하고 while 루프에서 마지막 세 점을 살펴보며 이 점들이 오른쪽 회전을 이루는지 확인할 수 있습니다. 그렇다면 가운데 점을 삭제해야 합니다. $p_{i-1}$을 포함하는 삼각형 $(p_0, p_i, p_{i-2})$를 찾았으므로 이 점은 삭제할 수 있습니다.

각 점은 한 번 추가되고 최대 한 번 제거되며, 이는 상수 번의 연산이 소요됩니다. 따라서 실행 시간은 정렬의 실행 시간, 즉 $O(n \log n)$에 의해 결정됩니다.

vector<r> graham(vector<r> points) {
    // находим p0, как и раньше
    r p0 = points[0];
    for (r p : points)
        if (p.x < p0.x || (p.x == p0.x && p.y < p0.y))
            p0 = p;

    // сортируем точки по полярному углу
    sort(points.begin(), points.end(), [&](r a, r b){
        return (a - p0) ^ (b - p0) > 0;
    });

    vector<r> hull;
    for (r p : points) {
        // удаляем последнюю точку со стека пока она образует невыпуклость
        while (hull.size() >= 2) {
            r new_vector = p - hull.back();
            r last_vector = hull.back() - hull[hull.size() - 2];
            // если два последних вектора заворачивают влево, удаляем последнюю точку
            if (new_vector ^ last_vector > 0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(p);
    }
    return hull;
}

주어진 점 집합에 대해 알고리즘의 모든 단계를 실행해 볼 수 있는 인터랙티브 시각화입니다.