볼록 껍질 시각화
Graham Scan 알고리즘으로 점 집합의 볼록 껍질을 구하는 과정을 단계별로 시각화합니다
기하학★★☆
속도
1 / 1점 수: 15껍질 꼭짓점: 0
점 개수15
기준점(최하단)스택현재 처리 중비교 중볼록 껍질 변
캔버스를 클릭하여 점을 추가하세요. 점을 드래그할 수 있습니다.
Graham Scan이 스택을 이용해 볼록 껍질을 구축하는 과정을 관찰하세요.
Graham Scan이 스택을 이용해 볼록 껍질을 구축하는 과정을 관찰하세요.
볼록 껍질이란?
볼록 껍질(Convex Hull)은 주어진 점 집합을 모두 포함하는 가장 작은 볼록 다각형입니다. Graham Scan은 O(n log n)에 볼록 껍질을 구하는 대표적인 알고리즘입니다.
사용 방법
- 1점 개수를 슬라이더로 조절하거나 캔버스를 클릭하여 직접 점을 추가하세요
- 2랜덤 또는 원형 배치 버튼으로 점을 생성하세요
- 3재생 버튼으로 Graham Scan 과정을 단계별로 관찰하세요
- 4주황색은 기준점, 보라색은 스택, 노란색은 현재 처리 중인 점입니다
- 5점을 드래그하면서 볼록 껍질이 어떻게 변하는지 확인하세요
동작 원리
- 1가장 아래에 있는 점을 기준점(pivot)으로 선택합니다
- 2나머지 점들을 기준점 대비 극각 기준으로 정렬합니다
- 3정렬된 순서대로 점을 스택에 push하며, 시계 방향 회전이면 pop합니다
- 4외적(cross product)으로 회전 방향을 판정합니다
- 5시간 복잡도: O(n log n). 공간 O(n)
실무 활용
- •충돌 감지 — 게임/CAD에서 복잡한 도형의 외곽선을 볼록 껍질로 근사
- •GIS — 도시의 서비스 영역, 배달 범위 등을 볼록 껍질로 표현
- •이미지 처리 — 윤곽선 검출 후 볼록 껍질로 물체 형상 분석
- •로봇공학 — 장애물 회피 경로 계획
비슷한 알고리즘
- •Graham Scan vs Jarvis March — Graham은 O(n log n) 보장, Jarvis는 O(nh)
- •Quickhull — 분할정복 기반 O(n log n) 평균
- •Andrew Monotone Chain — x좌표 정렬 후 상하 체인 구축
학습 팁
- •원형 배치에서는 모든 점이 껍질에 포함됩니다
- •내부 점이 많을수록 pop 연산이 자주 발생합니다
- •일직선 위의 점은 외적이 0이 되어 제거됩니다
- •점을 드래그하면서 직관을 쌓아보세요
자주 묻는 질문
Q. 볼록 껍질과 오목 껍질의 차이는?
A. 볼록 껍질은 모든 내각이 180도 이하, 오목 껍질은 알파 셰이프 등으로 더 정밀하게 감쌉니다.
Q. 시간 복잡도는?
A. O(n log n). 정렬이 지배합니다.
Q. 3D 볼록 껍질도 가능한가요?
A. 네, Quickhull 3D 알고리즘이 O(n log n)에 동작합니다.