2007년 11월 16일 금요일

2차원에서 임의의 한 점이 삼각형 내부에 있는지 판별하는 방법

프로그램 하나를 쪼물딱러리며 만들고 있는데,
임의의 한 점이 삼각형 내부에 있는지 판별하는 방법이 궁금해졌습니다.

이리저리 복잡하게 판단할 수도 있겠지만, 수학적으로 아름다운 방법이 없을까 찾아봤습니다.

그러다가 http://www.mathlove.org/pds/mathqa/faq/geometry/geometry49.html 에서 아래와 같은 답을 찾았습니다.

A=(x_1, y_1), B=(x_2, y_2), C=(x_3, y_3)라고 하고 주어진 점을 (a, b)라고 합시다. 그러면 삼각형의 내부는 아래 세 영역의 교집합입니다.

1. 직선 AB에 의해서 나뉘어 지는 두 영역 중에서 점 C가 속한 영역
2. 직선 BC에 의해서 나뉘어 지는 두 영역 중에서 점 A가 속한 영역
3. 직선 CA에 의해서 나뉘어 지는 두 영역 중에서 점 B가 속한 영역

예를 들어 1의 조건을 식으로 써보면, 직선 AB의 식은

f(x,y) = (x-x_1)(y_1-y_2)-(y-y_1)(x_1-x_2) = 0

이므로 점 C와 P가 같은 영역에 속하는지의 여부는 값

f(x_3, y_3)f(a, b)

의 부호를 살펴보면 됩니다. 양수이면 같은 영역, 음수이면 서로 다른 영역입니다. 이런 식으로 세번의 부등식 판별을 거치면 됩니다.


그 밑에는 간단하게 작성된 C 코드도 있더군요. 대단대단~
그런데, 조금 더 찾아보니 http://gpgstudy.com/forum/viewtopic.php?t=15797&sid=b280649b74e383b21261d6ec8426c5e1 에서 아래와 같은 어마어마한 내용을 찾았습니다.

삼각형이 v1, v2, v3 세점으로 이루어져 있을때
d1 = v2 - v1
d2 = v3 - v1

테스트 하고자 하는 점을 k 라고 할때
p = k - v1

그려면 2차원 상의 한 점 p는 d1과 d2의 선형 합으로 나타낼 수 있습니다.
t1 * d1 + t2 * d2 = p
위의 식을 연립 방정식으로 풀면 t1과 t2를 얻을 수 있습니다.

점 k가 삼각형 내에 있으려면

0 <= t1 <= 1
0 <= t2 <= 1
t1 + t2 <= 1

이 세가지 조건을 만족하면 됩니다.


수학의 세계는 너무나 아름답습니다.  수많은 수학자 여러분께 감사하단 인사를 드립니다. 꾸바닥!

댓글 1개: