Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 그레이엄 스캔(Graham Scan)으로 볼록 껍질(Convex Hull) 구현하기

개요

이 글에서는 주어진 점들의 집합에 대해 볼록 껍질(Convex Hull)을 구하는 C++ 프로그램을 소개합니다.

볼록 껍질이란 주어진 모든 점을 경계선 위 또는 내부에 포함하는 가장 작은 볼록 다각형을 의미합니다. 컴퓨터 그래픽스, 지리 정보 시스템(GIS), 충돌 감지 등 다양한 분야에서 활용되는 기본적인 기하학 알고리즘입니다.

그레이엄 스캔 알고리즘의 동작 원리

그레이엄 스캔(Graham Scan)은 다음과 같은 단계로 진행됩니다.

  1. 기준점 선택: y 좌표가 가장 작은 점을 찾습니다. y 좌표가 같은 점이 여러 개라면 x 좌표가 더 작은 점을 선택하여 기준점 p0으로 설정합니다.
  2. 정렬: 나머지 점들을 p0을 중심으로 반시계 방향 극각 순서대로 정렬합니다.
  3. 순회 및 판별: 정렬된 순서대로 점들을 탐색하면서 세 점의 방향(orientation)을 검사하고, 볼록 껍질의 경계에 해당하지 않는 점은 버립니다.

C++ 구현 예제

#include <iostream>
#include <stack>
#include <stdlib.h>
using namespace std;

struct Point {
    int x, y;
};

//다른 점들을 정렬할 때 기준이 되는 점
Point p0;

//스택의 최상단 바로 아래 요소를 반환
Point nextToTop(stack<Point> &S) {
    Point p = S.top();
    S.pop();
    Point res = S.top();
    S.push(p);
    return res;
}

//두 점의 위치 교환
void swap(Point &p1, Point &p2) {
    Point temp = p1;
    p1 = p2;
    p2 = temp;
}

//두 점 사이 거리의 제곱 계산
int distSq(Point p1, Point p2) {
    return (p1.x - p2.x)*(p1.x - p2.x) +
    (p1.y - p2.y)*(p1.y - p2.y);
}

//세 점의 방향 확인 (0: 일직선, 1: 시계 방향, 2: 반시계 방향)
int orientation(Point p, Point q, Point r) {
    int val = (q.y - p.y) * (r.x - q.x) -
    (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;
    return (val > 0)? 1: 2;
}

//qsort용 비교 함수: 극각 순서로 정렬
int compare(const void *vp1, const void *vp2) {
    Point *p1 = (Point *)vp1;
    Point *p2 = (Point *)vp2;
    int o = orientation(p0, *p1, *p2);
    if (o == 0)
    return (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1;
    return (o == 2)? -1: 1;
}

//볼록 껍질 계산 및 출력
void convexHull(Point points[], int n) {
    //y 좌표가 가장 작은 점 찾기
    int ymin = points[0].y, min = 0;
    for (int i = 1; i < n; i++){
        int y = points[i].y;
        if ((y < ymin) || (ymin == y &&
        points[i].x < points[min].x))
        ymin = points[i].y, min = i;
    }

    //가장 아래에 있는 점을 첫 번째 위치로 이동
    swap(points[0], points[min]);
    p0 = points[0];

    //나머지 점들을 p0 기준 극각 순서로 정렬
    qsort(&points[1], n-1, sizeof(Point), compare);

    //일직선상에 있는 점들 정리
    int m = 1;
    for (int i = 1; i < n; i++){
        while (i < n-1 && orientation(p0, points[i],
        points[i+1]) == 0)
            i++;
        points[m] = points[i];
        m++; //수정된 배열 크기 갱신
    }

    //점이 3개 미만이면 볼록 껍질을 만들 수 없음
    if (m < 3) return;

    stack<Point> S;
    S.push(points[0]);
    S.push(points[1]);
    S.push(points[2]);

    //나머지 점들을 처리하며 볼록 껍질 유지
    for (int i = 3; i < m; i++){
        while (orientation(nextToTop(S), S.top(), points[i]) != 2)
        S.pop();
        S.push(points[i]);
    }

    //결과 출력
    while (!S.empty()){
        Point p = S.top();
        cout << "(" << p.x << ", " << p.y <<")" << endl;
        S.pop();
    }
}

int main(){
    Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
    {0, 0}, {1, 2}, {3, 1}, {3, 3}};
    int n = sizeof(points)/sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

실행 결과

(0, 3)
(4, 4)
(3, 1)
(0, 0)

주요 함수 설명

  • nextToTop(): 스택의 최상단(top) 바로 아래에 있는 요소를 반환합니다. 스택의 내용은 변경되지 않습니다.
  • distSq(): 두 점 사이 거리의 제곱을 계산합니다. 실제 거리 연산보다 빠르며, 비교 목적에는 충분합니다.
  • orientation(): 세 점 p, q, r의 회전 방향을 판별합니다. 반환값 0은 세 점이 일직선상에 있음을, 1은 시계 방향, 2는 반시계 방향을 의미합니다.
  • compare(): qsort에 사용되는 비교 함수로, 기준점 p0을 중심으로 점들을 극각 순서대로 정렬합니다.
  • convexHull(): 기준점 탐색부터 정렬, 스택 연산까지 전체 알고리즘을 수행하고 최종 볼록 껍질을 출력합니다.

시간 복잡도

그레이엄 스캔의 시간 복잡도는 O(n log n)입니다. 대부분의 비용은 초기 정렬 단계에서 발생하며, 이후의 순회 과정은 각 점이 최대 한 번씩 push/pop 되므로 선형 시간에 처리됩니다.