어떤 점이 주어진 삼각형 내부에 있는지 외부에 있는지 판정하는 방법을 드디어 알아냈다. 자세한 증명은 좀 더 명확히 해 보도록 하고 일단 방법부터 설명하도록 한다.
삼각형에 있는 세개의 변 중에 임의의 2개를 고른다. 그리고 그 2개의 변을 양쪽으로 연장해서 평면을 4개로 분할한다. 적당히 그 4개의 분할된 영역을 분면이라고 하고, 1,2,3,4분면이라는 이름을 붙여두자.
[보조정리]
이제, 점이 삼각형 내부에 있다고 가정하자. 그럼 그 점은 반드시 4개의 분면중에 1개에는 들어 있어야 한다. “내부”라고 하였으므로 직선 위에 있는 경우는 없다.
또한, 나머지 한개의 변의 중점을 생각하자. 그 중점 역시 4개의 분면중에 1개에 들어가 있다.
점이 삼각형 내부에 있다면, 나머지 한 변의 중점과 주어진 점은 반드시 같은 분면에 들어간다.
[증명] 일단 생략
[정리]
어떤 점이 삼각형 내부에 있다면, 삼각형에 있는 3개의 변 중에서, 어떤 임의의 2개 변을 선택하더라도 나머지 한 변의 중점과 그 점은 같은 분면 안에 반드시 포함된다. 즉, 2개씩 고르는 작업을 3번 하면 삼각형 내부에 있는지 아닌지를 알아낼 수 있다.
[증명] 어쨌든 일단 생략
직관적으로는 일단 옳다는 결론을 내렸다. 상세한 증명은 그림을 좀 더 그려본 후에 작성해볼 예정이다.
——
더불어, 이 과정은 볼록다각형으로 확장할 수 있다. 볼록다각형은 한 점을 잡고서, 순서대로 점을 두개씩 골라가면 삼각형으로 분할할 수 있기 때문에 각각의 삼각형에 대해서만 판정하면 된다. 물론, 이 경우, 실제로 다각형의 변을 이루는 삼각형의 변과, 다각형 내부에 있는 삼각형의 변 중에서, 만약 그 점이 다각형 내부에 있는 삼각형의 변 위에 있다면 그것은 다각형 내부에 있다는 점을 염두하여 계산할 필요가 있다.
그리고 볼록다각형으로 확장한 다음에는 오목다각형을 포함할 수도 있다. 오목다각형은 볼록다각형 여러개로 잘라낼 수 있기 때문이다.
또한, 다시 이 과정을 다차원으로 확장할 수도 있다. 가령, 3차원의 경우에는 임의의 사면체에 대해서 먼저 증명하면 된다. 이 경우에는 사면체 중 꼭지점 하나를 공유하는 평면 3개를 정하고, 나머지 한 평면의 중점과 필요한 점이 8개의 분할된 공간 중 같은 공간에 속하는지를 판정하면 된다.
4차원에서도 가능할 것 같다. 이 경우에는 사면체 5개로 이루어진 초사면체에서 꼭지점 하나를 공유하는 사면체 4개를 정하고, 나머지 한 사면체의 중점과 필요한 점이 16개의 분할된 공간 중 같은 공간에 속하는지를 판정하면 된다. 물론, 복잡하다. -_-;
공리(Axioms)는 증명하지 않고 사용하는 것들이므로 물리학이든 수학이든 별 문제는 없습니다.
정리(Theorems)는, 물리학의 경우에는 수학적인 증명은 하지 않는 경우도 있습니다. 그러나, 그 경우에도 실험적인 근거는 갖고서 사용하는 것이기 때문에 증명되지 않은 것은 아닙니다.
물리학은 수학에서 사용하지 않는 (엄밀히 증명되지 않은) 수학적 공리(?)를 그대로 사용하는 경향이 있죠. ^^
다각형을 삼각형으로 나눈 선 위에 있는 점에 대한 논의는 본문에 되어 있구요
오목다각형으로 삼각형으로 나눌 때, 만약 겹쳐짐이 생기거나 엉뚱한 영역이 삼각형에 포함되어 버리면 곤란합니다. 겹쳐짐이나 엉뚱한 영역의 포함 없이 잘 나누려면 볼록다각형으로 쪼갠 다음에 다시 삼각형으로 나누는 것이 좋겠죠.
눈으로 보면 뻔한 것들이더라도 컴퓨터한테 시킬 때는 어떻게 될지 모르기 때문에, 완벽한 증명이 없는 한 가장 안전한 길로 가는 게 좋습니다.
오목다각형을 여러개의 삼각형으로 단숨에 잘라주는 알고리즘은 생각나질 않아서 말이죠.
그리고 수학이든 물리학이든 엄밀성을 추구하는 것은 마찬가지입니다. 그것이 어느 수준에서의 엄밀성이냐가 다르죠. 수학은 근거할 곳이 오직 공리와 논리밖에 없기 때문에 좀 더 추상적으로 엄밀하고, 물리학은 그 외에 실험에도 근거할 수 있기 때문에 덜 추상적일 뿐이라고 생각합니다.
오목다각형이건 볼록다각형이건 삼각형들로 쪼개질 수 있는 건 전혀 상관없잖아요.
그리고 그삼각형들 중 한 곳에 점이 있을 것이구요. 따라서 삼각형중 한 곳에 점이 포함됐는지를 살펴서 합계를 내면 되는 것이 아닐가 생각되네요. (엄밀히 말하자면 다각형을 삼각형으로 나눈 선 위에 점이 있을 수도 있으므로 좀 더 정밀한 알고리즘이 필요하겠네요.)
수학적인 것이랑은 별로 연관이 없을 것 같은데요. (뭐 수학분야에서 하는 것은 물리학보다 좀 더 엄밀성을 추구하는 것 같지만요.)
수학적으로는 우선 오목 다각형이 포함되어 있으면 볼록 다각형으로 쪼개고, 다시 그 볼록다각형을 삼각형으로 쪼개는 과정이 필요합니다. 무조건 직관적으로 “된다”고만 해서는 곤란합니다.
그리고 제가 만드는 알고리즘은 효율성과는 거리가 멉니다. 돌아가기만 하면 되거든요. 아무튼, 나름 독창적이지 않습니까?
삼각형에 해당하는 방법만 찾는다면 확장하여 다각형에 대입할 때는 볼록이건 오목이건 상관이 없습니다.
어차피 다각형을 삼각형으로 나눈 뒤에 하나씩 테스트하면 되니까요. ㅎㅎㅎㅎ
그보다는 컴퓨터 알고리즘으로 효율적으로 인증하는 방법을 찾아보시는 건 어떨까요?
Jordan의 곡선 정리와 같은 맥락일 겁니다.
(저게 맞다면, 어차피 동치인 정리니까요)
삼각형에 대해 주어진 정보가 3점의 위치밖에 없을 때, 밖으로 쏜 광선이 삼각형의 변을 지나가는지 안지나가는지 사람은 알기 쉽지만 컴퓨터는 알기 어렵습니다. 그래서 좀 다른 방법을 생각해 본 겁니다.
트랙백 읽어보시면 또다른 알고리즘도 있습니다.
광선을 쏘는 교과서적인 방법 이외의 다른 방식을 의도적으로 생각하신 건가요?