Convex Hull - Graham Scan

T -Strip LOD문서를 보다 Graham Scan알고리즘을 적용하여 convex hull을 구하는 부분이 나온다.

이 알고리즘은 O(N log N)의 시간복잡도를 가지는 convex hull을 구하는 알고리즘 이다.

방법

1. 정렬

 - 가장 아래의 왼쪽에 위치한 점을 기준으로 모든 점들을 반시계방향으로 정렬

2. 스캔

 - 기준점은 무조건 convex hull에 포함된다. 기준점을 스택에 넣고 두점까지 푸쉬한뒤 세번째 점부터

   마지막 점까지 스캔을 하는데, 항상 스택의 top, top-1, top-2가 반시계 방향을 이루게 push와 pop을한다. 그렇게 하다보면 남아있는 점들 모두 convex hull을 이루는 점들이 된다.