알고리즘: Convex Hull(컴벡스 헐), Graham Scan, Quick Hull

Convex Hull:

차원 평면에 여러개의 점이 있을 때, 그 점 중 일부를 이어서 나머지 점을 내부에 포함할 수 있는 볼록 다각형을 만드는 알고리즘.

볼록 다각형이란 다각형 내부의 두 점을 잇는 어떤 선분도 다각형 외부로 나가지 않는 단순 다각형

---

사전지식:

위 문제를 이해하기 위해서는 우선 CCW 알고리즘을 알아야한다.

https://qktjwl123.tistory.com/95

알고리즘: CCW(Counter Clock Wise)

 

또한 두개의 점을 주었을 때 두 점이 만드는 선분을 빗변,

y좌표가 더 낮은 점의 y값이 밑변이 되게하는 직각 삼각형의 각을 구하는 법을 알아야한다.

말로하면 어려우니 예시를 보자!

 여러 점을 주었을 때 y값이 제일 낮은 점이 기준점이 된다.

그 점을 기준으로 다른 점들을 다 잇고 밑변과 선분이 이루는 각을 구하는 것이다.

이는 arctan 함수로 구할 수 있지만 이를 코드로 구현하기엔 쉽지 않다.

우리는 정확한 각도가 아닌 각의 대소만 판단하면 된다.

따라서 실제 각이 아닌 dy/dx로 각을 대체한다.

(dx가 0이 되는 경우 90도임을 기억하자)

 

적용 예시:

(3,3), (4,4)가 있을 때 dy/dx-> (4-3)/(4-3)-> 1/1이다.

즉 각은 1로 볼 수 있다.

(3,3), (2,6)일 때는 dy/dx-> (2-3)/(6-3)-> -1/3이다.

각은 -1/3이다. 

 

+와 -를 따로 생각해서 정렬한 뒤 합쳐주면 된다.

(값의 절댓값이 큰 경우가 수직에 가까운 상태이다.)

 

사전 지식을 전부 알았으니 실제 알고리즘을 보자!

---

무식한 방법:

1. y가 가장 낮은 기준점 u를 잡는다.

2. 다른 모든 점이 선분 (u,v)의 왼쪽으로 가게하는 2번째 점 v를 정한다.

    (ccw로 각각의 점에 모든 다른 점을 돌려야한다.)

3. 2번을 무한반복한다..

 

사실 몰라도 되는 방식이다.

더 자세하게 알고 싶으면 타 블로그를 참고하자,,

https://blog.naver.com/rbdud96/221516203360

 

---

Graham scan: O(n log n)

1) y값이 가장 낮은 기준점을 하나 잡는다 (중복일 경우 x)

2) 다른점을 각에 따라 정렬한다. (1,2,3,...,n)

3) 점 1, 2를 잇는다.

4) 선분(1,2)를 기준으로 3번 점을 ccw로 확인한다. (점을 잇는 것은 stack에 push하는 방식)

4) 3번점이 왼쪽에 있는 것을 확인하고 점 2, 3을 잇는다.

5) 선분(2,3)을 기준으로 4번 점을 ccw로 확인한다.

6) 4번점이 왼쪽에 있는 것을 확인하고 점 3, 4을 잇는다.

7) 선분(3, 4)를 기준으로 5번 점을 ccw로 확인한다.

8) 5번점이 오른쪽에 있음을 확인하고 4번을 pop한다.

9) 선분(2,3)을 기준으로 5번을 ccw로 확인한다.

10) 오른쪽에 있음을 확인하고 점 3, 5를 잇는다.

11) 1번이 stack에 push될 때 까지 반복

 

 

시간복잡도: O(n log n)

    일단 점을 정렬하는데 O(n log n),

    n-1개의 점마다, 이전에 그은 선분 하나와 새로 그은 선분 하나의 왼쪽/오른쪽 관계를 한번씩 점검 : O(n)

    총 O(n log n)의 시간 복잡도를 갖게된다.

---

Quick Hull:  O(n log n) ~ O(n^2)

Quick Sort와 비슷하다.

분할정복 기법을 사용한다.

0. 좌우 끝점, 상하 끝점은 convex hull을 만드는 점에 항상 포함된다.

1. 그 중 두 점을 정한다. (가장 왼쪽 위 점, 가장 오른쪽 아래 점)

2. 두 점으로 선분을 만들고 점과 선 사이의 거리 공식을 사용하여 가장 먼 점을 컨백스 헐에 포함시킨다.

    이때 이 점은 항상 오른쪽에 위치해 있다. (가장 왼쪽 점을 기준으로 잡았기 때문)

3. 여기서 만들어진 삼각형 내부에 있는 점들은 전부 제거한다. (어차피 포함되어 있기 때문)

4. 새로 만들어진 선분과 남은 점으로 2~3을 반복한다. 

 

분석:

T(n) = O(n) + T(a) + T(b)

 

선분을 찾는데 O(n),

가장 먼 점을 찾는데 O(n)이다.

 

Best case로 점들이 최대로 삭제되면 O(n log n)

Worst case로 점들이 삭제가 안되면 O(n^2)의 시간복잡도를 갖게된다.