반응형 그라함 스캔 썸네일형 리스트형 볼록 껍질 (Convex Hull) 볼록 껍질 (Convex Hull) 볼록 껍질이란? "2차원 평면 상에서 주어진 점들을 모두 포함하는 가장 작은 다각형" (이 때, 다각형의 각 변들은 주어진 점을 양 끝점으로 갖는다) 기하 알고리즘에서 볼록 껍질이 자주 응용되기 때문에 중요한 알고리즘이다. 볼록 껍질을 구하는 데에는 '그라함 스캔 알고리즘(Graham's Scan Algorithm)'이 이용된다. 볼록 껍질 (Convex Hull) 구하는 과정은 다음과 같다. 1. 주어진 점들 중 y좌표가 가장 작거나 혹은 y좌표가 가장 작은 점이 둘 이상이라면 x좌표가 가장 작은 점을 선택 2. 선택한 점을 기준으로 나머지 점들을 반시계 방향으로 정렬 (각을 이용) 3. 그라함 스캔 알고리즘.. 이전 1 다음
