볼록 껍질 (알고리즘)

IT 위키
(볼록 껍질에서 넘어옴)

볼록 껍질(Convex Hull)은 2차원 평면상의 여러 점 집합에서, 모든 점을 포함하는 가장 작은 볼록 다각형을 의미한다. 쉽게 말해, 고무줄을 점들에 감쌌을 때 만들어지는 가장 바깥쪽 경계를 뜻하며, 계산기하학에서 매우 기본적이고 중요한 문제다.

1 개념[편집 | 원본 편집]

  • 점들이 모여 있는 형태에서 가장 바깥쪽을 둘러싸는 볼록 다각형을 찾는 문제
  • 볼록 다각형이란 두 점을 잇는 선분이 항상 다각형 내부에 포함되는 다각형을 의미함
  • 입력: n개의 점 (x, y)
  • 출력: 볼록 껍질을 이루는 점들의 리스트 (반시계 방향 정렬)
  • 목적: 가장 작은 다각형을 찾는 것이 목적이다. 가장 작다는 것은 일반적으로 테두리의 길이가 가장 작고 연결하는 꼭지점의 수가 작은 것을 의미한다. 아래 그림을 보면 면적은 (b)가 더 작지만 대부분의 알고리즘에서는 (a)를 최적의 답으로 선택한다.

볼록 껍질의 예시.png

2 응용[편집 | 원본 편집]

  • 컴퓨터 그래픽스 및 시각화
  • 충돌 감지, 경계 영역 계산
  • 지도 서비스에서의 범위 검색
  • 패턴 인식, 머신러닝의 군집 경계 계산

3 대표 알고리즘[편집 | 원본 편집]

3.1 1. 그레이엄 스캔(Graham Scan)[편집 | 원본 편집]

  • 입력 점들을 극각 기준으로 정렬 후 스택을 이용해 볼록 껍질 생성
  • 시간 복잡도: O(n log n)

절차 (상세 내용은 아래 소스코드 또는 문서 참고):

  1. 가장 y값이 작은 점을 기준점으로 설정
  2. 나머지 점들을 기준점에서의 각도(극각) 기준으로 정렬
  3. 시계 방향 회전하는 점은 제거하고 반시계 방향 점만 스택에 유지

3.2 2. Andrew's Monotone Chain[편집 | 원본 편집]

  • 점들을 x좌표 기준으로 정렬 후, 위쪽 껍질과 아래쪽 껍질을 각각 생성 후 병합
  • 시간 복잡도: O(n log n)

3.3 3. Jarvis March (Gift Wrapping)[편집 | 원본 편집]

  • 가장 왼쪽 점에서 시작하여 시계방향으로 외접하는 점을 차례로 선택
  • 시간 복잡도: O(nh) (h는 볼록 껍질에 속한 점의 수)
  • 작은 h에서는 빠름

3.4 4. Chan's Algorithm[편집 | 원본 편집]

  • Graham Scan과 Jarvis March를 결합
  • 시간 복잡도: O(n log h) — 이론적으로 가장 효율적

4 파이썬 예시[편집 | 원본 편집]

4.1 그레이엄 스캔[편집 | 원본 편집]

def cross(o, a, b):
    """벡터 OA × OB 의 z축 성분 (양수면 반시계 방향, 음수면 시계 방향)"""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def graham_scan(points):
    # 1. 중복 제거 + 정렬 (y 가장 작고, 같으면 x 가장 작은 점 기준)
    points = sorted(set(points))

    if len(points) <= 1:
        return points

    # 2. 아래쪽 껍질 만들기
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    # 3. 위쪽 껍질 만들기
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    # 4. 양쪽 껍질 합치기 (끝점 중복 제거)
    return lower[:-1] + upper[:-1]
points = [(0, 0), (1, 1), (2, 2), (3, 1), (2, 0), (1, -1)]
hull = graham_scan(points)
print("Convex Hull:", hull)
Convex Hull: [(0, 0), (1, -1), (3, 1), (2, 2)]

4.2 그레이엄 스캔 (극각 기반 구현)[편집 | 원본 편집]

def ccw(p1, p2, p3):
    return (p2[0]-p1[0])*(p3[1]-p1[1]) - (p2[1]-p1[1])*(p3[0]-p1[0])

def graham_scan(points):
    points = sorted(points, key=lambda p: (p[1], p[0]))
    pivot = points[0]
    sorted_pts = sorted(points[1:], key=lambda p: (atan2(p[1]-pivot[1], p[0]-pivot[0]), p))

    hull = [pivot]
    for pt in sorted_pts:
        while len(hull) >= 2 and ccw(hull[-2], hull[-1], pt) <= 0:
            hull.pop()
        hull.append(pt)
    return hull

5 같이 보기[편집 | 원본 편집]

6 참고 문헌[편집 | 원본 편집]