한 점이 삼각형 내부에 있는지를 체크하기

평면좌표상의 임의의 점 가 세 점 로 이루어진 삼각형 내부에 있는지 외부에 있는지를 판단하는 코드를 작성해보자. 이거 마치 무슨 고등학교 수학문제 같은데, 사실 고등학교 수학 문제 맞다…

좌표평면위에 와 임의의 점 가 있다고 가정하자. 오른쪽 그림에는 선분 에 대해서 점 와 점는 서로 다른 편에 있다. 어떤 점이 삼각형의 한 변에 대해서 나머지 꼭지점과 반대쪽에 있다면 그 점은 삼각형의 외부에 있는 것이다. 만약 점와 점가 같은 쪽에 있다면? 마찬가지로 선분 와 점, 선분 와 점에 대해서도 점 가 선분에 대해 나머지 점과 같은 방향에 있다면, 점가 내부에 있다고 말할 수 있다.

따라서 점를 삼각형의 모든 변에 대해서 각 변을 기준으로 그 대각꼭지점과 같은 쪽에 있다는 것을 확인하면 점 는 내부에 존재하는 것으로 확인할 수 있다. 그럼 두 점이 한 선분에 대해서 같은쪽에 있는지, 다른쪽에 있는지는 어떻게 확인할 수 있을까? 그 방법만 안다면 될 것이다.

모든 점에 좌표성분을 알고 있다고 가정한다면, 다시 위 그림에서 선분와 선분를 직선으로 확장해서 두 개의 직선에 대한 식을 얻고, 이를 연립해서 교점을 찾는다. 그리고 교점이 네 점의 좌표값의 최대/최소 구간 내에 있는지를 확인하면 반대쪽에 존재하는 것으로 확인할 수 있을 것이다. 그런데 이 계산은 귀찮다. 조금 더 편한 방법이 있을까?

벡터의 외적을 사용하면 어떤 선분을 기준으로 선분 밖의 두 점이 같은 쪽에 위치하는지, 아니면 다른쪽에 위치하는 지를 알 수 있다. 사실은 두 개의 벡터가 직선으로 확장됐을 때 서로 교차하는지를 검사하는 것이다. 그 방법은 아래와 같다.

외적을 구하려면 3차원 벡터가 되어야 하므로, 위 상황은 좌표 공간에서 인 좌표 평면위라고 가정하자. 그리고 선분 를 벡터 로 본다. 이 벡터의 시작점 에서 를 향하는 벡터 도 알 수 있겠다. 이 때 를 기준으로 와 를 각각 구한다, 이렇게 구해진 두 벡터의 내적을 구해 그 값이 0보다 크거나 같다면 두 점 는 이 를 기준으로 같은 쪽에 있다고 판단한다.

이 방법을 사용하면 결국 각 좌표값들의 간단한 곱셈과 덧셈만으로 같은 쪽에 존재하는지 여부를 파악할 수 있다. 그리고 이 것을 최대 3번 반복하면 점 P가 삼각형ABC의 내부에 존재하는지 알 수 있게 된다.

일단 간단하게 줄리아에서 이를 어떻게 계산할 수 있는지 살펴보자.

외적을 구하려면 3차원 벡터가 필요하므로, 각 점의 z좌표는 0이라고 둔다. Julia는 기본적으로 벡터 타입을 다룰 수 있기 때문에 다음과 같이 간단하게 함수를 작성할 수 있다. ( crossProduct 함수는 줄리아 1.1.0 부터 LinearAlgebra 패키지의 cross 함수로 옮겨졌음)

using LinearAlgebra
function isSameSide(a, b, p, q)
  c1 = cross(b-a, p-a)
  c2 = cross(b-a, q-a)
  c1' * c2 >= 0
end

참고로 위 코드에서 c1'는 c1의 전치행렬(행과 열을 서로 바꾼 행렬)이며, transpose(c1)와 같다.

이제 점 가 내에 존재하는지 여부를 살펴보는 함수를 작성해보자. 앞서 말한바와 세 변에 대해서 isSameSide를 적용해보고, 모두 true가 되는지 체크하면 된다. 따라서 점과 삼각형의 꼭지점을 받아서 내부에 있는지를 체크하는 함수는 다음과 같이 작성된다.

isInside(p, a, b, c) = all([isSameSide(a, b, c, p),
                            isSameSide(b, c, a, p),
                            isSameSide(c, a, b, p)])

참 쉽죠?

이 문제를 파이썬으로 푸는 방법은 벡터를 클래스로 구현하기에서 예제로 소개하고 있다.

참고 – 벡터의 외적 계산 방법

두 3차원 벡터 (x1, x2, x3)와 (y1, y2, y3)가 있을 때 외적의 1, 2, 3번째 요소는 각 요소의 다음번째의 요소에 대해서 대각곱을 구하면 된다. 말로 설명하면 좀 이상할 거 같은데, 다음을 보자.

    x1  x2  x3  x1
          \/
          /\
    y1  y2  y3  y1
z1 = x2y3 - x3y2

z2의 경우에는 x3에서 출발하므로 x3y1 – x1y3가 된다. 이런식으로 계산할 수 있다.

function crossProduct(a, b)
  x1, x2, x3 = a
  y1, y2, y3 = b
  return [x2*y3 - x3*y2;
          x3*y1 - x1*y3;
          x1*y2 - x2*y1]
end

Swift 예시

다음은 Swift로 이 연산을 구현한 코드이다. 먼저 공간상의 한 점을 나타내기 위한 Point3D 타입을 정의한다. 이는 한 점을 정의하는 동시에 원점에서 그 점까지를 연결하는 벡터로 사용될 수 있다. 따라서 선분 AB는 A – B로 표현될 것이기 때문에 이 타입에 대한 – 연산자를 오버로드해준다.

또한 내적을 계산하는 함수도 작성해주어야 한다. * 연산자를 오버로딩하는 것도 좋은 아이디어 겠다.

struct Point3D {
 let x: Float
 let y: Float
 let z: Float
  init(x: Float, y:Float, z:Float=0) {
    self.x = x
    self.y = y
    self.z = z
  }
  static func -(lhs: Point3D, rhs: Point3D) -> Point3D {
    return Point3D(x: lhs.x - rhs.x,
                   y: lhs.y - rhs.y,
                   z: lhs.z - rhs.z)
  }
}
// 외적을 계산하는 함수
func crossProduct(_ a: Point3D, _ b: Point3D) -> Point3D {
  return Point3D(x: a.y * b.z - a.z * b.y,
                 y: a.z * b.x - a.x * b.z,
                 z: a.x * b.y - a.y * b.x)
}
// 내적을 계산하는 함수
func dotProduct(_ a: Point3D, _ b:Point3D) -> Float {
  return a.x * b.x + a.y * b.y + a.z * b.z
}
// 선분AB를 기준으로 두 점 P, Q가 같은쪽에 있는지를 검사한다.
func isSameSide(_ a:Point3D, _ b: Point3D, _ p: Point3D, _ q: Point3D) -> Bool {
  let c1 = crossProduct(b - a, p - a)
  let c2 = crossProduct(b - a, q - a)
  return dotProduct(c1, c2) >= 0
}
let a = Point3D(x:0, y:0)
let b = Point3D(x:100, y:100)
let p = Point3D(x:10, y:1)
let q = Point3D(x:1, y:10)
let r = Point3D(x:1, y:11)
print(isSameSide(a, b, p, q))
print(isSameSide(a, b, r, q))