Monotone Chain 알고리즘(볼록 껍질, Convex Hull)

오늘은 boj slack을 눈팅하다가 알게된 Convex Hull을 구하는 알고리즘을 소개하려고 합니다.

Convex Hull이란?

• Convex Hull은, 평면의 경우 입력으로 들어온 정점들 중 일부를 꼭지점으로하는 볼록 다각형입니다.

Convex Hull을 구하는 알고리즘

Graham Scan

• Graham스캔은 먼저, 아무 정점이나 하나 잡습니다(보통, y좌표가 가장 작은 점을 기준점으로 잡는다고 합니다. 그리고 이 점은 반드시 Convex Hull에 포함됩니다.)
• 그리고 이 점들을 기준으로 CCW방향으로 정렬을 해줍니다.
• 무슨 뜻이냐 하면, 선택한 한 점이 x축 위에 있다고 가정하고 그 점과 그 점을 제외한 모든 점이 이루는 각도를 계산합니다. 그 다음, 계산한 각도가 작은 순으로 나열하면 CCW방향으로 정렬을 한 것입니다.
• 그리고 stack을 하나 만든 뒤, 첫 번재 정점과 두 번째 정점을 넣습니다.
  -> 스택에서 맨 윗 점을 뺍니다(second), 처음에 넣은 두 점(first, second)을 제외한 다음 점을 last라고 하겠습니다. first(stack의 top), second, last가 CCW인지 확인한 후, CCW라면 볼록껍질이 될 수 있다는 의미이므로 pop했던 second를 다시 stack에 넣어주고 last도 stack에 넣어줍니다. CW라면(!CCW) 마지막으로 마지막으로 뺀 정점(second)을 버리고, last를 넣습니다.
• 위 과정을 배열 전체를 순회할 때 까지 반복합니다.
• 그림으로 된 자세한 설명은 Crocus님의 블로그에 있습니다.
  Graham Scan은 각도에 대해 정렬해줘야한다는 점이 까다롭습니다. 그리고 구현을 하게 되면 코드가 길어지기때문에 조금 번거롭습니다.

Monotone Chain

• Monotone Chain은 정점들을 각도에 대해 정렬할 필요가 없습니다. 간단하게 말하면 Convex Hull을 윗껍질, 아래껍질로 나누어 합치는 것인데요. 이때 나누어지는 윗 껍질과 아래 껍질은 시작점과 끝 점을 공유합니다.
• 알고리즘은 간단합니다. 정점들을 한 축(x나 y 아무거나)에 대해 정렬합니다. x축에 대해 정렬한다고 하면, x좌표가 작은 순서대로 정렬하고 x축의 좌표가 같으면 y축의 값이 작은 순서대로 정렬해줍니다. 사실 Graham Scan처럼 Stack을 하나 만든 뒤 윗 껍질을 구하는 경우엔 CCW 방향으로 점들을 삽입해주면 됩니다.
• 아래 껍질을 구하는 경우, 정렬한 점을 뒤집어서 마찬가지로 CCW 방향으로 Stack에 삽입해 주면 됩니다.
• 마지막으로 윗 껍질과 아래 껍질을 합치면 Convex Hull이 됩니다. 
• 윗 껍질과 아래 껍질이 양 끝 점을 공유하므로 잘 제외시켜주면 됩니다.
• 자세한 설명과 구현은  남남서님의 블로그에 정리되어 있습니다.