삼각형 내부에 있는 점 판정하기

어떤 점이 주어진 삼각형 내부에 있는지 외부에 있는지 판정하는 방법을 드디어 알아냈다. 자세한 증명은 좀 더 명확히 해 보도록 하고 일단 방법부터 설명하도록 한다.

삼각형에 있는 세개의 변 중에 임의의 2개를 고른다. 그리고 그 2개의 변을 양쪽으로 연장해서 평면을 4개로 분할한다. 적당히 그 4개의 분할된 영역을 분면이라고 하고, 1,2,3,4분면이라는 이름을 붙여두자.

[보조정리]
이제, 점이 삼각형 내부에 있다고 가정하자. 그럼 그 점은 반드시 4개의 분면중에 1개에는 들어 있어야 한다. "내부"라고 하였으므로 직선 위에 있는 경우는 없다.
또한, 나머지 한개의 변의 중점을 생각하자. 그 중점 역시 4개의 분면중에 1개에 들어가 있다.
점이 삼각형 내부에 있다면, 나머지 한 변의 중점과 주어진 점은 반드시 같은 분면에 들어간다.

[증명] 일단 생략

[정리]
어떤 점이 삼각형 내부에 있다면, 삼각형에 있는 3개의 변 중에서, 어떤 임의의 2개 변을 선택하더라도 나머지 한 변의 중점과 그 점은 같은 분면 안에 반드시 포함된다. 즉, 2개씩 고르는 작업을 3번 하면 삼각형 내부에 있는지 아닌지를 알아낼 수 있다.

[증명] 어쨌든 일단 생략

직관적으로는 일단 옳다는 결론을 내렸다. 상세한 증명은 그림을 좀 더 그려본 후에 작성해볼 예정이다.


------
더불어, 이 과정은 볼록다각형으로 확장할 수 있다. 볼록다각형은 한 점을 잡고서, 순서대로 점을 두개씩 골라가면 삼각형으로 분할할 수 있기 때문에 각각의 삼각형에 대해서만 판정하면 된다. 물론, 이 경우, 실제로 다각형의 변을 이루는 삼각형의 변과, 다각형 내부에 있는 삼각형의 변 중에서, 만약 그 점이 다각형 내부에 있는 삼각형의 변 위에 있다면 그것은 다각형 내부에 있다는 점을 염두하여 계산할 필요가 있다.

그리고 볼록다각형으로 확장한 다음에는 오목다각형을 포함할 수도 있다. 오목다각형은 볼록다각형 여러개로 잘라낼 수 있기 때문이다.

또한, 다시 이 과정을 다차원으로 확장할 수도 있다. 가령, 3차원의 경우에는 임의의 사면체에 대해서 먼저 증명하면 된다. 이 경우에는 사면체 중 꼭지점 하나를 공유하는 평면 3개를 정하고, 나머지 한 평면의 중점과 필요한 점이 8개의 분할된 공간 중 같은 공간에 속하는지를 판정하면 된다.

4차원에서도 가능할 것 같다. 이 경우에는 사면체 5개로 이루어진 초사면체에서 꼭지점 하나를 공유하는 사면체 4개를 정하고, 나머지 한 사면체의 중점과 필요한 점이 16개의 분할된 공간 중 같은 공간에 속하는지를 판정하면 된다. 물론, 복잡하다. -_-;