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

좌표평면위에 와 임의의 점
가 있다고 가정하자. 오른쪽 그림에는 선분
에 대해서 점
와 점
는 서로 다른 편에 있다. 어떤 점이 삼각형의 한 변에 대해서 나머지 꼭지점과 반대쪽에 있다면 그 점은 삼각형의 외부에 있는 것이다. 만약 점
와 점
가 같은 쪽에 있다면? 마찬가지로 선분
와 점
, 선분
와 점
에 대해서도 점
가 선분에 대해 나머지 점과 같은 방향에 있다면, 점
가
내부에 있다고 말할 수 있다.
따라서 점를 삼각형의 모든 변에 대해서 각 변을 기준으로 그 대각꼭지점과 같은 쪽에 있다는 것을 확인하면 점
는
내부에 존재하는 것으로 확인할 수 있다. 그럼 두 점이 한 선분에 대해서 같은쪽에 있는지, 다른쪽에 있는지는 어떻게 확인할 수 있을까? 그 방법만 안다면 될 것이다.
모든 점에 좌표성분을 알고 있다고 가정한다면, 다시 위 그림에서 선분와 선분
를 직선으로 확장해서 두 개의 직선에 대한 식을 얻고, 이를 연립해서 교점을 찾는다. 그리고 교점이 네 점의 좌표값의 최대/최소 구간 내에 있는지를 확인하면 반대쪽에 존재하는 것으로 확인할 수 있을 것이다. 그런데 이 계산은 귀찮다. 조금 더 편한 방법이 있을까?
벡터의 외적을 사용하면 어떤 선분을 기준으로 선분 밖의 두 점이 같은 쪽에 위치하는지, 아니면 다른쪽에 위치하는 지를 알 수 있다. 사실은 두 개의 벡터가 직선으로 확장됐을 때 서로 교차하는지를 검사하는 것이다. 그 방법은 아래와 같다.
외적을 구하려면 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))