[알고리즘] convex hull(컨벡스 헐)

계산 기하

• 2/3차원 공간상에서 점, 선, 도형 간의 관계를 다루는 문제
• 실생활에 매우 밀접하게 응용된다.

일단 2차원 공간/정수 좌표/정수 연산으로 가정한다.

→ 가급적 +,-,*,>,=,<만 가급적 쓴다.

→ sin, cos, tan, / 최대한 피한다.

💡 이유: round-off error❗️

Polygon(convex hull을 위한 build-up)

• 선분들로 이루어진 닫혀진 도형
• n개의 점과 n개의 선분이 다음 조건을 만족한다.
  •  
• 점 하나를 잡고 같은 방향으로 이어지는 리스트.
• 꼭짓점을 타고 가는 과정에서 선분들이 엇갈리는 경우는 없다고 가정한다. ⇒ 현실적인 다각형을 위해서.

모든 점을 지나는 경로

n개의 점이 주어졌을 때, 이 점을 모두 지나서 처음 시작점으로 돌아오는 경로를 구하시오. 단, 이 경로는 중간에 서로 교차하지 않는 일이 없다.

• 기하 문제에서 자주 등장하는 조건 : 세 개의 점이 같은 직선에 있는 경우는 없다. → 예외가 많이 발생하는 경우.

해법 : 가장 y좌표가 낮은 점을 기준점으로 잡는다. 다음, 이 점을 지나는 직선과, 이 점과 다른 점들을 잇는 직선을 구한 뒤, 각의 크기에 따라 정렬한다. 이 순서대로 방문하면 된다.

각이 큰 순서? tan를 알아야 한다.

• tan(기울기)는 a/b로 표현 가능하다. 실수로 바꾸지 않고, 통분으로 대소 관계를 비교한다. 하지만 이 경우는 기울기가 음수일 때 적용 불가능하기 때문에 나보다 왼쪽/오른쪽인 두 가지 경우로 케이스를 나눈다.

---

convex hull

n개의 점이 주어졌을 때, 이 점을 모두 포함하는 가장 작은 볼록 다각형.

♦︎ k개의 점을 골라서 볼록 다각형을 만드는 과정을 말한다.

조건1) 다각형 밖에는 다른 점이 없다.
조건2) 이 다각형은 볼록 다각형이다.

 

오목vs볼록 판단

• 내각의 크기가 모두 180 이내이면 볼록, 180 이상이 존재하면 오목.
• 안에 두 점을 잡아서 이은 점이 테두리와 교차하는 점이 없으면 오목, 있으면 볼록

제일 무식한 방법

1. 제일 위 점, 제일 아래 점을 기준으로 차례대로 돌려본다. → 아이디어는 분명하지만 구현하다가 미침ㅋㅋ

단순 무식 방법

1. 가장 y좌표가 작은 점을 기준점 u로.
2. 다른 모든 점이 선이 다른 모든 점이 선분 (u, v)의 왼쪽으로 가는 점 v를찾는다.
3. 이제 v에서 다시 2번 조건을 만족하는 점을 찾는다. 💡 빙글빙글 돌린다❗️
4. u로 돌아오면 끝!

시간 복잡도 : (n-1) * (n-2) + (n-2) * (n-3) + ... + 2 * 1 = O(n**3)

 

Graham scan: O(n log n) 방법

개념적으로 convex hull은 sorting이랑 똑같다. 알고리즘에서 sorting 배울 때 구하는 방법이 정말 많음을 느꼈을 것이다. convex hull도 마찬가지이다.

1. 앞과 같이 기준점 u를 찾는다.(이때 이 점은 반드시 컨벡스 헐에 포함된다.)
2. 다른 점들을 각에 따라 정렬한다.

• 각을 정렬했으므로 가장 작은 각인 오른쪽부터 탐색을 시작한다.

Graham scan 과정

같은 방향??? (강의 내용 42분 쯤에 나옴)

4번째 그림에서 모든 점이 내 왼쪽에 있다고 가정했기에 오른쪽에 점이 있으면 안된다.

 

[분석]

• 점을 정렬하는 데에 O(n log n)
• n-1개의 점마다 총 2번씩 체크(왼쪽인지? 오른쪽인지?) 총 상수시간 * n

 

... 다음 시간에 이어서 작성할 예정.