볼록 껍질 (Convex Hull)

개요

정의는 '모든 점을 포함하는 가장 작은 볼록다각형' 이다.
- 작다는 것은, 면적을 기준으로 해도 되고, 둘레의 길이를 기준으로 해도 된다.
문제에서 주어지는 다른 표현들로는 이런 것들이 있다.
- 임의의 점 3개로 만들어지는 삼각형들의 합집합
최적 시간 복잡도는 O(nlogn). O(nlogh)도 있긴 하지만..
널리 알려진 O(nlogn) 알고리즘 은 두가지이다.
Graham scan 과 monotone chain
더 널리 알려진것? 은 Graham scan 이다
바닥상태에서 짜기 쉬운 것은 monotone chain이다. Graham scan은 점들의 각도정렬을 할줄 알아야 한다.
속도는..
- Graham scan의 각도 정렬을 ccw를 써서 하면 monotone chain보다 느리다
- Graham scan의 각도 정렬을 x/y 값을 사용하고, 최적화하면 monotone chain보다 빨라진다
  - monotone chain은 upper hull과 lower hull을 각각 계산하기 위해서 모든 점을 이터레이션 하는 것을 두번 반복해야 하는데, Graham scan은 한번으로 된다.

각도 정렬을 시킬때, 각도로만 정렬하는 방법과 (각도, 거리)으로 정렬하는 방법(각도가 같을때는 거리가 짧은것이 앞서도록) 이 있다.
기본적으로는 각도로만 정렬해도 충분하지만, 이 때에는 가장 작은 각도에 해당되는 점과 가장 큰 각도에 해당되는 점이 여러개일경우를 따로 처리해줘야 한다.
- 가장 작은 각도에 해당되는 점들 중에서는 거리가 가장 큰 점을 선택해야 한다.
- 만약 3개 이상이 점이 한 직선상에 있는 경우를 모두 볼록껍질에 포함시키기로 결정했다면, 이 점들을 거리순으로 정렬해야 한다.
(각도, 거리)로 정렬하는 것은 가장 작은 각도에 해당되는 점과 가장 큰 각도에 해당되는 점이 여러개일때, 이것들을

같은 점이 두개 이상 있는 경우?
- 이걸 허용하면 골치아프다. 허용하지 말자
3개 이상이 점이 한 직선상에 있는 경우?
- 이건 처리해줘야 한다. 모든 점을 볼록껍질에 포함시킬건지, 양 끝점만 볼록껍질에 포함시킬건지를 결정해야 한다.
모든 점이 한 직선상에 있는 경우?
- 예외 취급 해야하나? 응