3D 기하 (Geometry) 기본

정의

3D 기하 는 3차원 공간 (x, y, z) 위의 점, 직선, 평면, 벡터를 다루는 분야. PS 에서는 정육면체 / 구 / 원뿔 체적, 3D convex hull, 최근접 점 3D 등이 등장. 2D 기하의 cross/dot product 를 3차원으로 확장한 것이 핵심.

문제 상황과 동기

3D 공간에서는 2D 에 비해 고려할 자유도가 1 추가되어 직관을 벗어나는 상황이 많음.

• 2D: 점 이외에도 직선(1D) 만 있음. 선분 교차 = CCW 4회.
• 3D: 점 + 직선(1D) + 평면(2D). 두 직선은 꼬인 위치(skew) 가능. 외적 결과가 벡터.
• 직선과 평면의 교차: 매개변수 방정식 풀이 필요.

핵심 통찰: 3D 외적은 두 벡터에 수직인 벡터(법선) 를 반환. 이 법선으로 평면의 방정식을 세우고, 직선과의 교차점, 점과 평면의 거리를 모두 O(1) 에 계산.

시각화

핵심 아이디어

3D 벡터 연산

평면의 방정식

점 P0(x0, y0, z0) 를 지나고 법선 n = (nx, ny, nz) 인 평면:
    nx*(x - x0) + ny*(y - y0) + nz*(z - z0) = 0
    -> nx*x + ny*y + nz*z + d = 0    (d = -nx*x0 - ny*y0 - nz*z0)

직선의 매개변수 방정식

점 P0, 방향 v = (vx, vy, vz):
    P(t) = P0 + t * v    (t 는 실수)

알고리즘

점과 평면의 거리

plane_distance(P, nx, ny, nz, d):
    return |nx*P.x + ny*P.y + nz*P.z + d| / sqrt(nx*nx + ny*ny + nz*nz)

직선과 평면의 교차

line_plane_intersection(P0, v, nx, ny, nz, d):
    denom = v.x*nx + v.y*ny + v.z*nz
    if denom == 0: return "평행 또는 평면 위"
    t = -(nx*P0.x + ny*P0.y + nz*P0.z + d) / denom
    return P0 + t * v

구현

// 3D 벡터: 외적, 내적, norm, 평면 거리
#include <bits/stdc++.h>
using namespace std;
struct Vec3 { double x, y, z; };
Vec3 cross(Vec3 a, Vec3 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(Vec3 a, Vec3 b) { return a.x*b.x + a.y*b.y + a.z*b.z; }
double norm(Vec3 a) { return sqrt(dot(a, a)); }
int main() {
  Vec3 u{1, 0, 0}, v{0, 1, 0};
  Vec3 w = cross(u, v);
  printf("u x v = (%.0f, %.0f, %.0f)\n", w.x, w.y, w.z);
  printf("|u x v| = %.2f\n", norm(w));
  printf("u . v = %.0f\n", dot(u, v));
  // 평면 방정식: z = 0 (법선 (0,0,1), d = 0)
  auto dist = [](Vec3 p, Vec3 n, double d) {
      return fabs(dot(p, n) + d) / norm(n);
  };
  Vec3 n{0, 0, 1}, p{1, 2, 3};
  printf("점(1,2,3) - 평면 z=0 거리: %.2f\n", dist(p, n, 0));
}

# 3D 벡터 연산 (numpy 없이)
import math
def cross(a, b):
  return (a[1]*b[2] - a[2]*b[1], a[2]*b[0] - a[0]*b[2], a[0]*b[1] - a[1]*b[0])
def dot(a, b): return a[0]*b[0] + a[1]*b[1] + a[2]*b[2]
def norm(a): return math.sqrt(dot(a, a))
​
u, v = (1, 0, 0), (0, 1, 0)
w = cross(u, v)
print(f"u x v = {w}")
print(f"|u x v| = {norm(w):.2f}")
print(f"u . v = {dot(u, v)}")
​
# 평면 z=0 까지 점 (1,2,3) 의 거리
n, d = (0, 0, 1), 0
dist = abs(dot((1,2,3), n) + d) / norm(n)
print(f"점-평면 거리: {dist:.2f}")

import java.util.*;
public class Main {
  static class Vec3 { double x, y, z;
      Vec3(double x, double y, double z) { this.x = x; this.y = y; this.z = z; }
  }
  static Vec3 cross(Vec3 a, Vec3 b) {
      return new Vec3(a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x);
  }
  static double dot(Vec3 a, Vec3 b) { return a.x*b.x + a.y*b.y + a.z*b.z; }
  static double norm(Vec3 a) { return Math.sqrt(dot(a, a)); }
  public static void main(String[] args) {
      Vec3 u = new Vec3(1,0,0), v = new Vec3(0,1,0);
      Vec3 w = cross(u, v);
      System.out.printf("u x v = (%.0f, %.0f, %.0f)%n", w.x, w.y, w.z);
      System.out.printf("|u x v| = %.2f%n", norm(w));
      System.out.printf("u . v = %.0f%n", dot(u, v));
      Vec3 n = new Vec3(0,0,1);
      double d = 0;
      Vec3 p = new Vec3(1,2,3);
      double dist = Math.abs(dot(p, n) + d) / norm(n);
      System.out.printf("점-평면 거리: %.2f%n", dist);
  }
}

u x v = (-0, 0, 1)
|u x v| = 1.00
u . v = 0
점-평면 거리: 3.00

복잡도

변형 / 활용

1. 3D Convex Hull

점들을 감싸는 최소 볼록 다면체. QuickHull (O(N log N)) 이 일반적. 결과는 삼각형 메시. 2D convex hull 과 달리 face(면) 의 법선 방향이 중요.

2. 직선과 직선의 최단 거리

꼬인 위치(skew) 에서 두 직선의 최단 거리는 외적으로 계산:

skew_distance(P1, v1, P2, v2) = |(P2 - P1) . (v1 x v2)| / |v1 x v2|

3. 구와 직선의 교차

직선 매개변수 방정식을 구에 대입, 2차 방정식 풀이. 판별식으로 접하는지 / 통과하는지 판정.

4. 회전 변환 (Rotation)

3D 회전은 오일러 각 또는 쿼터니언(quaternion) 으로 표현. 외적이 회전축을 결정.

함정

1. 평행 / 수직 판정

|a x b| 가 0 에 가까우면 두 벡터는 평행 (collinear). dot(a, b) 가 0 에 가까우면 수직. 각각 EPS 비교.

2. 법선 방향 (Right-hand rule)

3D 외적 a x b 는 right-hand rule 을 따름. 왼손 좌표계(예: Unity) 에서는 반대 방향.

3. 정수 좌표의 한계

3D 에서도 정수 좌표가 가능하지만, 외적 결과가 long long 범위를 초과할 수 있음. 부동소수점 사용 또는 __int128 (C++) 필요.

4. 평면의 네 가지 표현

점-법선 / 일반형 / 세 점 / 두 직선. 문제에 따라 적절히 변환 필요.

BOJ 연습 문제

참고

• 2D 기하 기본
• 3D Convex Hull
• CCW (시계/반시계 판정)