helloktk의 블로그 | ㅇ http://blog.naver.com/helloktk/80025507906 평면상의 영역이 convex하다는 의미는 그 영역에 속하는 임의의 두점을 연결하는 선분상의 모든 점들 또한 해당영역에 속하는 경우을 의미한다. 점들의 모임에서 convex hull을 찾는 것은 점들을 잇는 선분자체가 포함되는 다각형을 찾는 것을 의미한다. 간단하게 생각할 수 있는 방법은 최외각의 한점을 기준으로해서(점들을 감싸는 최소 사각형상의 한점) 그 자신을 뺀 모든 점들이 왼편이나 일직선상에 놓일수 있는 점을 찾는다. 다시 이 찾은 점을 기준으로 나머지점들에 대해서 동일한 조건을 만족하는 점들을 차례로 찾으면, 주어진 점들을 감싸는 최소의 점들의 모임을 구할 수 있고, 이것이 convex hull을 구성한다(Gift Wrap). 이 알고리즘은 n개의 점들에 대해서 각각 O(n)정도의 찾기를 시도하므로 전체적으로 O(n^2)정도의 스텝이 필요한 알고리즘이다. 여기서 찾는 과정을 좀더 빠르게 할 수 있다면 전반적인 알고리즘의 복잡도도 감소한다. 따라서 점들은 우선 일정한 순서대로 정열을 하고난 후에 순차적으로 들어오는 점들이 왼편에 있는가만 판별하면 되는 과정으로 줄일 수 있다. 이제 conex hull을 구하는 알고리즘중에서 잘알려진 Graham Scan 알고리즘을 살펴보도록 하자. 이 알고리즘은 앞에서 설명한 과정을 그대로 따라 진행이 되는데, 우선 점들을 맨 바깥쪽에 있는 한점 (점들을 감싸는 최소 사각형상의 임의의 한점이면 충분하다. 보통은 최저의 y값을 갖는 점들중에 최대의 x값을 갖는 점으로 기준점으로 잡는다)을 기준으로 해서 각도의 크기로 점들을 정열을 해 둔상태에서 진행이 된다. 정열방법은 기준점을 각도를 계산하여 정열을 할 수 있으나, 각도수치계산의 부정확성과 복잡...