벡터 내적·외적과 거리

내적: 같은 방향 성분

n차원 벡터 u = (u₁, …, uₙ), v = (v₁, …, vₙ)의 내적(dot product)은

u · v = u₁v₁ + u₂v₂ + … + uₙvₙ = |u||v|cos θ

내적 값	의미
u · v > 0	사이각이 예각, 대체로 같은 방향
u · v = 0	수직 (영벡터가 아닐 때)
u · v < 0	둔각, 반대 방향

(u · v) / |v|는 u를 v 방향으로 내린 정사영(projection)의 길이다. "v 방향으로 얼마나 가 있나"를 재는 자로 쓸 수 있다.

점과 초평면 사이의 거리

n차원 공간에서 a₁x₁ + … + aₙxₙ + d = 0을 만족하는 점들의 집합을 초평면(hyperplane) 이라 한다. 2차원에서는 직선, 3차원에서는 평면이다. 계수를 모은 벡터 n = (a₁, …, aₙ)으로 쓰면 초평면은 n · x + d = 0이다.

계수 벡터는 법선이다

초평면 위의 두 점 p, q는 모두 n · p + d = 0, n · q + d = 0을 만족한다. 빼면 n · (q − p) = 0. 평면 위의 어떤 방향 벡터와도 내적이 0이므로 n은 초평면에 수직인 법선 벡터다. 예: 평면 z = 0(xy 평면)의 법선은 (0, 0, 1)이다.

거리 공식

점 P에서 초평면까지의 거리는 초평면 위의 아무 점 Q에서 P로 가는 벡터 P − Q를 법선 방향으로 정사영한 길이다. 평면과 평행한 성분은 거리에 기여하지 않는다.

dist = |n · (P − Q)| / |n|
     = |n · P − n · Q| / |n|
     = |n · P + d| / |n|            (Q가 평면 위의 점이라 n · Q = −d)
 
3차원:  |a·x₀ + b·y₀ + c·z₀ + d| / √(a² + b² + c²)
2차원 (점과 직선):  |a·x₀ + b·y₀ + c| / √(a² + b²)

학교에서 외우는 두 공식은 차원만 다른 같은 식이다. 절댓값을 떼면 부호가 점이 법선 쪽에 있는지 반대쪽에 있는지를 알려 준다. 선형 분류기(퍼셉트론, SVM)가 w · x + b의 부호로 클래스를 가르고 크기로 확신도를 재는 것도 같은 원리다.

2차원 외적: 방향과 넓이

2차원 벡터 u = (u₁, u₂), v = (v₁, v₂)의 외적(cross product)은 스칼라 하나로 쓴다. 3차원 외적의 z 성분이다.

u × v = u₁v₂ − u₂v₁ = |u||v|sin θ

외적 값	의미
u × v > 0	v가 u의 반시계 방향(왼쪽)에 있다
u × v = 0	평행(한 직선 위)
u × v < 0	v가 u의 시계 방향(오른쪽)에 있다

|u × v|는 u, v가 만드는 평행사변형의 넓이다. 그래서 외적은 계산 기하의 기본 연산이 된다.

CCW (세 점의 방향)

def ccw(a, b, c):
    # a→b 벡터와 a→c 벡터의 외적: 양수면 반시계, 음수면 시계, 0이면 일직선
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

쓰임	방법
선분 교차 판정	두 선분 AB, CD에 대해 `ccw(A,B,C)·ccw(A,B,D) ≤ 0`이고 `ccw(C,D,A)·ccw(C,D,B) ≤ 0` (일직선이면 범위 겹침을 따로 확인)
다각형 넓이	꼭짓점을 순서대로 돌며 외적을 더해 절반: 신발끈 공식
볼록 껍질	점을 정렬하고 CCW로 오목하게 꺾이는 점을 버린다
점과 직선 거리	`

점이 삼각형 안에 있는가

삼각형 ABC와 점 P에 대해 d1 = ccw(A, B, P), d2 = ccw(B, C, P), d3 = ccw(C, A, P)를 구한다. P가 안쪽이면 세 변을 같은 방향으로 돌 때 P가 늘 같은 쪽에 있으므로 세 값의 부호가 모두 같다. 양수와 음수가 섞이면 바깥이다. 0이 있으면 변 위다.

def in_triangle(a, b, c, p):
    d = [ccw(a, b, p), ccw(b, c, p), ccw(c, a, p)]
    has_neg = any(x < 0 for x in d)
    has_pos = any(x > 0 for x in d)
    return not (has_neg and has_pos)        # 변 위도 안쪽으로 친다 (제외하려면 0도 검사)

같은 판정을 넓이로도 할 수 있다. P로 삼각형을 셋으로 나눈 넓이(외적의 절댓값의 절반)의 합이 원래 넓이와 같으면 안쪽, 크면 바깥이다. 부호 있는 넓이를 그대로 더하면 P가 어디에 있든 합이 같아지므로 반드시 절댓값을 취한다. 세 작은 삼각형 넓이를 전체 넓이로 나눈 비율이 무게중심 좌표(barycentric coordinates) 이고, 세 값이 모두 0 이상이면 안쪽이다. 부호 비교 방식이 나눗셈이 없어 더 간단하고 정확하다.

직선 기준 정렬

방향 벡터 d를 가진 직선(기준점 p₀)에 대해 각 점 p를

cross(d, p − p₀)로 정렬하면 직선에서 떨어진 부호 있는 거리 순서,
dot(d, p − p₀)로 정렬하면 직선을 따라간 위치 순서가 된다.

두 값을 (외적, 내적) 순으로 비교하면 직선을 평행 이동하며 점을 하나씩 넘기는 스위핑의 순서가 된다. 실제 거리가 아니라 순서만 필요하므로 |d|로 나누지 않는다. 그래서 정수 좌표라면 정수 연산만으로 정확하게 비교할 수 있다. 부동소수점 거리를 쓰면 같은 줄 위의 점이 오차로 갈라질 수 있다.

자주 쓰는 판정

기하는 대개 문제의 주제가 아니라 다른 알고리즘의 부품이다. 2차원에서 자주 쓰는 판정은 제곱근과 나눗셈 없이 할 수 있다.

판정	방법
두 점의 거리 비교	`dx² + dy²`끼리 비교한다. 제곱근은 단조 증가라 순서가 같으므로 계산할 필요가 없다. 원점에서 가장 가까운 k개 점은 이 값으로 크기 k 힙을 쓴다
두 원이 겹치는가	중심 사이 거리의 제곱이 반지름 합의 제곱보다 작으면 겹친다: `dx² + dy² < (r1 + r2)²`
축에 평행한 두 직사각형이 겹치는가	x축과 y축에서 각각 구간이 겹쳐야 한다: `a.left < b.right and b.left < a.right and a.bottom < b.top and b.bottom < a.top`. 1차원 구간 겹침(스위핑)을 두 번 쓰는 셈이다

변의 길이·넓이·좌표가 0인 경우가 가장 자주 놓치는 경계 사례다. 넓이 0인 직사각형, 반지름 0인 원, 원점 위의 점, 모서리만 닿는 경우를 겹침으로 칠지 먼저 정한다. 등호를 넣느냐가 답을 가른다.

정리

내적 = 같은 방향 성분. 0이면 수직, ÷|v|면 정사영 길이
초평면 n · x + d = 0의 계수 벡터 n은 법선이고, 점과의 거리는 |n · P + d| / |n|
2차원 외적 = 방향(부호)과 넓이(크기). CCW 하나로 교차·넓이·볼록 껍질·거리·삼각형 내부 판정을 처리한다.
계산 기하에서는 나눗셈을 미루고 정수 외적·내적으로 비교해 오차를 피한다.

관련 노트: 벡터공간과 부분공간, 스위핑, 퍼셉트론과 다층 퍼셉트론

버그 제보