# 3D Convex Hull

3D Convex Hull은 3차원 점 집합을 모두 포함하는 가장 작은 convex polyhedron의 face를 구하는 계산기하 심화 주제입니다. 2D Convex Hull처럼 정렬 한 번으로 끝나지 않고, face orientation, visible face 제거, horizon edge 구성, coplanar degeneracy 처리가 핵심입니다.

## 문제 신호

| 문제 표현 | 3D Convex Hull 관점 |
| --- | --- |
| 3차원 점들의 외피 면 개수 | convex polyhedron |
| 모든 점을 포함하는 최소 다면체 | hull faces |
| 어떤 점이 hull 밖에 있는지 판정 | visible face |
| Delaunay lifting이나 regular triangulation | lower hull |
| face normal과 면적 합이 필요 | oriented triangle faces |

3D hull은 구현량이 크고 degeneracy에 민감합니다. 입력 크기가 작거나 정확도가 낮아도 되는 문제인지 먼저 확인합니다.

## Signed Volume

점 `a, b, c`가 만드는 oriented face에 대해 점 `p`가 어느 쪽에 있는지는 부호 있는 부피로 봅니다.

```text
volume6(a, b, c, p) = dot(cross(b-a, c-a), p-a)
```

부호가 양수이면 face normal 방향 쪽, 음수이면 반대쪽입니다. face 방향을 바깥쪽으로 맞춰 두면 `volume6 > 0`인 점에서 그 face가 보입니다.

## Predicate 구현 조각

아래 코드는 3D hull 구현의 가장 작은 predicate 묶음입니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <cmath>
using namespace std;

struct Point3D {
    double x = 0;
    double y = 0;
    double z = 0;
};

Point3D operator-(Point3D a, Point3D b) {
    return {a.x - b.x, a.y - b.y, a.z - b.z};
}

Point3D cross(Point3D a, Point3D b) {
    return {
        a.y * b.z - a.z * b.y,
        a.z * b.x - a.x * b.z,
        a.x * b.y - a.y * b.x
    };
}

double dot(Point3D a, Point3D b) {
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

double signedVolume6(Point3D a, Point3D b, Point3D c, Point3D p) {
    return dot(cross(b - a, c - a), p - a);
}

bool visibleFrom(Point3D a, Point3D b, Point3D c, Point3D p) {
    const double eps = 1e-10;
    return signedVolume6(a, b, c, p) > eps;
}
```

정수 좌표가 크면 `long long` 곱셈이 넘칠 수 있습니다. 그 경우 `__int128` predicate 또는 exact arithmetic 정책을 따로 잡아야 합니다.

## Incremental Hull 흐름

대표 구현은 사면체를 초기 hull로 만든 뒤 점을 하나씩 추가합니다.

```text
for each point p:
  visible faces = p에서 보이는 face
  if none: p is inside or on hull
  horizon edges = visible face와 invisible face의 경계
  remove visible faces
  add faces from horizon edge to p
```

horizon edge 방향을 잘못 잡으면 새 face normal이 안쪽을 보게 됩니다. face를 추가할 때 내부 기준점이나 기존 invisible face 방향으로 orientation을 맞춥니다.

## 작은 예시

```text
초기 tetrahedron:
  A(0,0,0), B(1,0,0), C(0,1,0), D(0,0,1)

새 점 P(1,1,1)
P에서 보이는 face들을 제거하고,
보이는 영역의 boundary edge에 P를 붙여 새 삼각형 face를 만든다.
```

2D hull에서 바깥 점이 보이는 edge 구간을 대체하는 것과 비슷하지만, 3D에서는 경계 edge의 방향과 면 인접 정보를 일관되게 유지해야 합니다.

## Coplanar 처리

| 상황 | 처리 선택 |
| --- | --- |
| coplanar point를 face 위 점으로 보존 | face polygon 병합 필요 |
| triangular face만 필요 | 기존 face 내부의 점은 제외 가능, 바깥으로 확장하는 점은 처리 |
| 모든 boundary point 필요 | face별 2D hull 재구성 |
| floating input | EPS 정책 일관성 필요 |

대부분의 contest 구현은 triangular face list를 반환합니다. 문제에서 "hull 위 점 개수"를 요구하면 coplanar boundary point도 세야 하므로 별도 처리가 필요합니다.

## Lower Hull과 Lifting

2D Delaunay나 Power Diagram은 3D lifting으로 설명할 수 있습니다.

```text
(x, y) -> (x, y, x^2 + y^2)
lower convex hull projection -> Delaunay triangulation
```

따라서 3D hull predicate는 고급 Voronoi/Delaunay 구현의 기반이 됩니다. 다만 실제로 robust Delaunay를 만들려면 incircle predicate와 degeneracy 처리가 추가로 필요합니다.

## 시간 복잡도

3차원 볼록 다면체의 꼭짓점이 V개이면 삼각분할한 최종 면 수는 최대 2V-4로 O(N)입니다. 매 삽입마다 모든 현재 면을 훑는 단순 incremental 방식은 O(N²)이며, random shuffle만으로 O(N log N)이 되지는 않습니다. 더 빠른 기대 시간에는 conflict graph 등 추가 구조가 필요합니다. 모든 점 삼중항과 나머지 점을 검사하는 검산법은 O(N⁴)입니다.

일반 위치의 볼록 다면체에 바깥 점을 추가할 때 horizon은 하나의 닫힌 경계입니다. 일직선·동일 평면 입력은 초기 사면체를 만들 수 없으므로 저차원 hull로 분기합니다. 같은 평면에 있다는 이유만으로 새 점을 버리면 기존 면 밖으로 확장하는 점을 놓칩니다.