두 직선의 교점 구하기 (외적)

수학 외적으로 두 직선의 교점을 구해보자. 게임 개발자에게는 필수 교양으로 알아두면 좋다.
두 직선이므로 포인트 xy 값으로 4개 있다.

먼저 성분들을 살펴보자.

점의 homogeneous 좌표 표현(2D)

• (x, y) -> (x, y, 1)
• p = (x, y, 1)

두 점(p1, p2)의 외적로서의 직선(line)

• line = p1 * p2

두 직선(line1, line2)의 교점 (homogeneous)

• v = line1 * line2
• v = (x, y, w)

점의 2D 좌표로 변환

• (x, y, w) -> (x/w, y/w)

예시로 풀어보기 (파이썬)

이제 실제 데이터를 제공하고 두 직선의 교점을 찾아서 원리를 이해해보자.
먼저, 두 직선 2개를 제공해 교점을 구하는 코드를 작성할 것이다.

• 직선 1:
  • p1 = (0, 0)
  • p2 = (1, 2)
• 직선 2:
  • p3 = (0, 2)
  • p4 = (2, 0)

이러한 두 직선은 서로 교차되는 교점(homogenous)인 xy 값을 찾는 것이 목표이다.
수식은 앞에서 설명했으므로 바로 코드로 작성한다.

import numpy as np
import matplotlib.pyplot as plt

# 1. 점 정의
p1 = np.array([0, 0])
p2 = np.array([1, 2])
p3 = np.array([0, 2])
p4 = np.array([2, 0])

# 2. homogenous 좌표로 변환 (x, y) -> (x, y, 1)
def to_homogeneous(p):
  return np.array([p[0], p[1], 1])

ph1 = to_homogeneous(p1)
ph2 = to_homogeneous(p2)
ph3 = to_homogeneous(p3)
ph4 = to_homogeneous(p4)

# 3. 두 점을 직선으로 표현 (외적)
line1 = np.cross(ph1, ph2) # [-2 1 0]
line2 = np.cross(ph3, ph4) # [2 2 -4]

# 4. 두 직선 -> 교점 (외적)
intersection_h = np.cross(line1, line2) # [-4 -8 -6]

# 5. homogeneous -> 2D 좌표 값
intersection = intersection_h[:2] / intersection_h[2]

print("교점 (x, y): ", intersection)

교점 (x, y): [0.66666667 1.33333333]

시각적으로 확인하고 싶다면 파이썬에서 아래 코드를 덧붙이자.

# 시각화
plt.figure()
plt.plot([p1[0], p2[0]], [p1[1], p2[1]], label="Line 1")
plt.plot([p3[0], p4[0]], [p3[1], p4[1]], label="Line 2")
plt.scatter(intersection[0], intersection[1], label="Intersection")
plt.legend()
plt.xlabel("x")
plt.ylabel("y")
plt.title("Intersection using Homogeneous Coordinates")
plt.show()

외적(cross) 구하기

numpy 라이브러리 cross 사용해서 내부에 어떻게 동작하는지 볼 수가 없었는데, 확인하고 싶으면 아래 자바스크립트 코드를 살펴보면 쉽게 이해할 수 있다.

function cross(a, b) {
  const a0 = a[1] * b[2] - a[2] * b[1];
  const b0 = a[2] * b[0] - a[0] * b[2];
  const c = a[0] * b[1] - a[1] * b[0];
  return [a0, b0, c];
}

외적을 단순하게 보면 포인트(x, y)처럼 보여서 처음 배울 때 당황했는데, 포인트가 아닌 새로운 선의 방정식으로 암시적으로 생각해야만 이해하기가 쉬워진다.

외적 방정식

• ax * by * c = 0

앞에서 구한 line1 = [-2 1 0] 예시로 사용해,
라인 [-2 1 0] 데이터를 방정식에 사용하면 -2x * y * 0 = 0 표현할 수 있다.
값 x와 y을 제공할 때 방정식 계산에 따라 0이 되어야 직선인 것이다.

교점 방정식

앞에서 파이썬으로 두 라인의 외적 방정식을 구했다.

• line1: -2x * y * 0 = 0
• line2: 2x * 2y * -4 = 0

위의 방정식을 참고하여 임의의 변량 [x, y] 주어서 직선과 함께 계산한다.

• line1 * [x, y] = 0
• line2 * [x, y] = 0

각각 직선과 점을 대입하여 0이 되어야만 서로 교차되는 지점이 되고,
두 라인이 비로소 교점이자 내적이 만들어진다.