컨벡스 헐은 공간 상의 포인트들을 모두 포함하는 가장 작은 볼록 다각형을 말합니다. 쉽게 말해, 포인트들을 고무로 둘러싼 모양이라고 생각할 수 있습니다.

알고리즘

2D Hull

1. $x$ 좌표가 최소/최대인 두 포인트를 찾고, 컨벡스 헐의 시작 부분으로 구성합니다.
2. 이 두 포인트를 연결한 엣지를 기준으로, 나머지 포인트들을 두 부분집합으로 분할합니다.
3. 각 부분집합에서 엣지로부터 가장 먼 포인트을 찾아 폴리곤을 형성합니다.
4. 폴리곤 내부의 포인트들은 제외하고, 새로운 엣지에 대해 과정을 재귀적으로 반복합니다.
5. 더 이상 포인트가 남지 않을 때까지 반복합니다.

3D Hull

<aside> <img src="/icons/dialogue_blue.svg" alt="/icons/dialogue_blue.svg" width="40px" />

2D와의 차이점

1. 2D에서는 엣지와 그 양쪽의 포인트들을 처리하지만, 3D에서는 트라이 폴리곤과 그 위아래의 포인트들을 처리합니다.
2. 알고리즘의 시작 단계에서 사면체(tetrahedron)를 구성합니다.
3. 재귀적 처리 과정에서 각 포인트는 최대 3개의 새로운 페이스와 연결될 수 있습니다. </aside>

아이디어