볼록 껍질 (알고리즘)
IT 위키
(볼록 껍질에서 넘어옴)
볼록 껍질(Convex Hull)은 2차원 평면상의 여러 점 집합에서, 모든 점을 포함하는 가장 작은 볼록 다각형을 의미한다. 쉽게 말해, 고무줄을 점들에 감쌌을 때 만들어지는 가장 바깥쪽 경계를 뜻하며, 계산기하학에서 매우 기본적이고 중요한 문제다.
1 개념[편집 | 원본 편집]
- 점들이 모여 있는 형태에서 가장 바깥쪽을 둘러싸는 볼록 다각형을 찾는 문제
- 볼록 다각형이란 두 점을 잇는 선분이 항상 다각형 내부에 포함되는 다각형을 의미함
- 입력: n개의 점 (x, y)
- 출력: 볼록 껍질을 이루는 점들의 리스트 (반시계 방향 정렬)
- 목적: 가장 작은 다각형을 찾는 것이 목적이다. 가장 작다는 것은 일반적으로 테두리의 길이가 가장 작고 연결하는 꼭지점의 수가 작은 것을 의미한다. 아래 그림을 보면 면적은 (b)가 더 작지만 대부분의 알고리즘에서는 (a)를 최적의 답으로 선택한다.
2 응용[편집 | 원본 편집]
- 컴퓨터 그래픽스 및 시각화
- 충돌 감지, 경계 영역 계산
- 지도 서비스에서의 범위 검색
- 패턴 인식, 머신러닝의 군집 경계 계산
3 대표 알고리즘[편집 | 원본 편집]
3.1 1. 그레이엄 스캔(Graham Scan)[편집 | 원본 편집]
- 입력 점들을 극각 기준으로 정렬 후 스택을 이용해 볼록 껍질 생성
- 시간 복잡도: O(n log n)
절차 (상세 내용은 아래 소스코드 또는 문서 참고):
- 가장 y값이 작은 점을 기준점으로 설정
- 나머지 점들을 기준점에서의 각도(극각) 기준으로 정렬
- 시계 방향 회전하는 점은 제거하고 반시계 방향 점만 스택에 유지
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 참고 문헌[편집 | 원본 편집]
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press
- Computational Geometry: Algorithms and Applications by de Berg et al.
- https://cp-algorithms.com/geometry/convex-hull.html