직선은 평면을 두개로 나눈다

평면 위에 직선이 하나 있다고 하자. 그 직선은 무한히 먼 곳에서 시작하여 무한히 먼 곳에서 끝난다. 낭만적이지 않은가? 그렇게 길게 이어진 직선은 평면을 두 영역으로 나눈다. 그것이 남과 북이 되었든, 좌와 우가 되었든 문제는 되지 않는다. 평면 위에 있는 모든 점은 따라서 평면에 있는 세개의 부분집합 중 하나에 반드시 포함된다. 왼쪽에 있거나, 오른쪽에 있거나, 또는 직선 위에 있거나. 그중에 없다면 이 점은 평면 위에 있는 점이 아니다.

직선의 방정식은 일반적으로 다음과 같다.

$ax+by+c=0$

이 방정식에다가 어떤 점 (p,q)가 세 집합 중 어디에 있는지 알아보려면?

이렇게 하면 될 것 같다.

$ap+bq+c < 0$ : 왼쪽
$ap+bq+c=0$ : 직선 위

$ap+bq+c >$ 0 : 오른쪽

(여기서, 왼쪽이냐 오른쪽이냐는 전혀 시각적인 이미지가 아니며, 대충 말로 정한 값이다.)

따라서, 어떤 점 두개 (p,q)와 (r,s) 가 있을 때, 직선이 나누는 세 영역 중에서 같은 쪽에 있는지 확인하려면 다음과 같이 하면 된다.

$sgn(ap+bq+c)*sgn(ar+br+c) > 0 $ : 같은쪽

$sgn(ap+bq+c)*sgn(ar+br+c) < 0 $: 다른쪽
$sgn(ap+bq+c)*sgn(ar+br+c) = 0 $: 둘 중 한놈이 직선 위에 있는 놈이다.

그래서, 일단 벡터가 주어졌을 때 직선의 방정식을 한번 써 보자.

벡터가 (x1,y1), (x2,y2) 라고 한다면

$y=\frac{y2-y1}{x2-x1} (x1-x) +y1$

이 수식을 $ax+by+c$ 형태로 바꾸면

$a=y2-y1$

$b=x1-x2$

$c=y1*x2-x1*y2$

이 된다.

이제, 삼각형 내부에 점이 있는지 없는지 판정하는 함수를 만들 준비가 끝났다.