Convex hull (볼록 껍질)

[1. 개요]

컨벡스 헐(이하 볼록 껍질) 이란?

• 평면 위 N개의 점이 주어졌을 때,
• M 개의 점을 이용하여, 나머지 모든 점을 내부에 포함하게 만드는 도형.
• 즉, 모든 점을 포함하는 볼록 다각형 중, 면적이 최소인 다각형을 말한다.

---

[2. 알고리즘 - 개요]

컨벡스 헐을 구하는 알고리즘은 아래와 같은 것들 있다.

1. Graham scan (그라함 스캔)
2. Jarvis march
3. Divide & Conquer

여기서 가장 유명한 알고리즘이 그라함 스캔이라고 한다.

그라함 스캔의 동작 방식은 아래와 같다.

1. 주어진 점을 y 순으로 정렬한다. (y 가 같은 경우는 x 순으로 정렬)
2. 정렬 된 점 중 첫번째 점을 기준으로 반시계 방향으로 나머지 점들을 정렬한다.
3. 정렬 된 점 들 중, 처음 2 개의 점을 스택에 푸쉬한다.
4. 그 다음 점이,  스택의 가장 마지막으로 푸쉬 된 두점을 기준(순서 중요) 으로, 왼편에 온다면, 해당 점을 스택에 푸쉬한다.
5. 그 다음 점에 대하여 4번을 다시 수행한다.

---

[3. 알고리즘 - 상세]

먼저, 1번 단계 , 대신 2번 단계 반시계 방향으로 정렬하는 방법은 아래와 같다.

 

평면 상의 3개의 점이 있을 때, 두점을 이용하여  직선을 만들고, 나머지 한 점이 이 직선에 어느 편에 오는지 확인하려면.

벡터의 외적을 이용해야 한다. (아래글 참조)

• 벡터 외적 관련 url

평면 상에서는 두 직선의 모두 수직인 z 축의 값이 0 보다 크면 점이 직선의 왼편에 있게 된다.

벡터의 외적을 이용하여, 점이 직선에 어느 편에 오는지는 직선의 방향에 의해 결정된다.

---

 

[구현]

• https://testkernelv2.tistory.com/724
•