[Algorithm] 컨벡스 헐 만들기(Convex Hull), Graham Scan

아래 그림과 같은 점들이 있다고 하자.

 

모든 점들을 이어서 다각형을 만들고 싶다면 어떻게 할 수 있을까?

 

1. 가장 먼저 y 좌표가 가장 작은 점을 기준으로 잡고 다른 점들과 모두 연결한다.

 

2. 기준으로 잡은 점을 관통하는 x축에 수평인 직선을 긋고 각도를 계산한 후 작은 순서대로 번호를 매긴다.

3. 번호 순서대로 연결한다.

위와 같은 방식으로 모든 점을 지나는 다각형이 완성되었다.

 

물론 당연하게도 이 다각형 외에도 여러 모양의 다각형을 만들 수 있다.

 

각도 알아내기

점들을 각도 순서대로 정렬하려면 각도를 알아낼 수 있어야 한다.

 

각도를 알아내는 방법은 탄젠트 값을 구한 다음에 탄젠트의 역 함수인 아크 탄젠트 함수에 넣으면 구할 수 있다.

 

그런데 여기서는 정확한 각도를 알아내는 것이 중요한 것이 아니라 점들끼리 각도의 대소 관계만 알아내면 된다.

 

라이브러리에 있는 아크 탄젠트를 사용해도 되지만 단순히 CCW로 각도를 비교해도 된다.

 

다각형 내부에 점 존재 여부

판별을 원하는 점을 기준으로 한 쪽 방향으로 직선을 긋는다.

 

직선과 만나는 점의 개수가 짝수면 점이 다각형 외부에 존재한다는 뜻이고 홀수면 점이 다각형 내부에 존재한다는 뜻이다.

 

교차 여부는 CCW 알고리즘을 사용해서 알 수 있다.

https://growth-coder.tistory.com/163

[Algorithm][백준 11758][파이썬] CCW 알고리즘을 활용하여 선분의 교차 여부 판단

Convex Hull 구하기

Convex Hull은 볼록 다각형, 즉 모든 각이 180도 이내인 사각형이다.

 

컨벡스 헐의 중요한 성질은 어떠한 두 점을 이어도 다각형이 두 점을 이은 선분을 반드시 포함해야 한다.

 

Graham Scan

Graham Scan은 컨벡스 헐을 구하기 위한 알고리즘이다.

 

우선 위에서 구한 다각형은 컨벡스 헐이 아니다. 만약 해당 점들을 모두 포함하는 컨벡스 헐을 만든다면 다음과 같은 모습일 것이다.

 

이를 구하기 위해서는 위에서 기준 점을 잡고 각도 순으로 정렬하는 것까지는 동일하다.

 

여기서 중요한 점은 점에서 점으로 이동할 때마다 반드시 같은 방향으로 이동해야 한다는 점이다.

 

좌회전만 허용할 예정이다.

과정

 

우선 기준점과 기준점을 기준으로 각도가 가장 작은 점을 이어서 선분(빨간색)을 만든다.

 

선분을 만든 두 점을 제외한 점들 중 각도가 작은 점들(초록색)부터 비교를 시작한다.

 

초록 점은 빨간 선분에 비해서 왼쪽에 존재한다. CCW 알고리즘으로 외적을 하면 알 수 있다.

 

(자세한 설명은 위에 걸어놓은 CCW 링크 참조.)

 

왼쪽에 있으므로 다음 점으로 넘어간다.

 

 

 

오른쪽에 존재하는 모습을 볼 수 있다. 이럴 경우 선분 중 각도가 더 큰 점을 버린다.(하늘색)

또 오른쪽에 있으니까 또 버리고 다음 점으로 넘어간다.

 

이번엔 왼쪽에 존재한다. 잇는다.

 

다시 오른쪽이다 버린다. 이를 반복하면 최종적으로 아래와 같은 모습이다.