Blog Content

  • [기하/개념] 볼록 껍질 (Convex Hull)

    Category 개발레시피/└ Algorithm on 2017. 12. 1. 20:16

    1. list[] 에 있는 점들 중 가장 작은 것을 찾아서 기준점으로 선정한다.2. 기준점 기준으로 각각의 점들을 반시계 방향으로 기준점과 각도 순서대로 정렬한다.3. 점들을 하나씩 보면서 볼록껍질에 포함시킬지 말지를 결정한다.스택을 하나 만들고, 이 스택에는 점의 번호를 넣어주는데 스택 사이즈가 한개밖에 없으면일단 지금 잡고 있는 점을 넣는다.스택에 점이 두 개 이상이면 비교를 한다.점 두개를 기준으로 다른 점을 봤을 때 CCW를 하는데, 이 때 반시계 방향에 있으면 만족하므로 스택에 넣어준다.그리고나서 또 스택의 두개를 빼서 두 점 기준으로 다음 점을 CCW 한다.만약 반시계 방향에 없다면 오목하다는 의미이므로 만족하지 않는다. 따라서 이럴 경우에는 스택에서 빼준다.이렇게 계속 반복해준다. 12345..

    Read more