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

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

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

[증명] 일단 생략

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

[증명] 어쨌든 일단 생략

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


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

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

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

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

by snowall 2008.08.27 23:50
  • ㄹㄹㄹ 2008.08.28 12:22 ADDR EDIT/DEL REPLY

    광선을 쏘는 교과서적인 방법 이외의 다른 방식을 의도적으로 생각하신 건가요?

    • snowall 2008.08.28 13:45 신고 EDIT/DEL

      Jordan의 곡선 정리와 같은 맥락일 겁니다.
      (저게 맞다면, 어차피 동치인 정리니까요)

      삼각형에 대해 주어진 정보가 3점의 위치밖에 없을 때, 밖으로 쏜 광선이 삼각형의 변을 지나가는지 안지나가는지 사람은 알기 쉽지만 컴퓨터는 알기 어렵습니다. 그래서 좀 다른 방법을 생각해 본 겁니다.
      트랙백 읽어보시면 또다른 알고리즘도 있습니다.

  • goldenbug 2008.08.29 13:50 신고 ADDR EDIT/DEL REPLY

    삼각형에 해당하는 방법만 찾는다면 확장하여 다각형에 대입할 때는 볼록이건 오목이건 상관이 없습니다.
    어차피 다각형을 삼각형으로 나눈 뒤에 하나씩 테스트하면 되니까요. ㅎㅎㅎㅎ

    그보다는 컴퓨터 알고리즘으로 효율적으로 인증하는 방법을 찾아보시는 건 어떨까요?

    • snowall 2008.08.29 23:51 신고 EDIT/DEL

      수학적으로는 우선 오목 다각형이 포함되어 있으면 볼록 다각형으로 쪼개고, 다시 그 볼록다각형을 삼각형으로 쪼개는 과정이 필요합니다. 무조건 직관적으로 "된다"고만 해서는 곤란합니다.
      그리고 제가 만드는 알고리즘은 효율성과는 거리가 멉니다. 돌아가기만 하면 되거든요. 아무튼, 나름 독창적이지 않습니까?

    • goldenbug 2008.08.30 02:02 신고 EDIT/DEL

      오목다각형이건 볼록다각형이건 삼각형들로 쪼개질 수 있는 건 전혀 상관없잖아요.
      그리고 그삼각형들 중 한 곳에 점이 있을 것이구요. 따라서 삼각형중 한 곳에 점이 포함됐는지를 살펴서 합계를 내면 되는 것이 아닐가 생각되네요. (엄밀히 말하자면 다각형을 삼각형으로 나눈 선 위에 점이 있을 수도 있으므로 좀 더 정밀한 알고리즘이 필요하겠네요.)

      수학적인 것이랑은 별로 연관이 없을 것 같은데요. (뭐 수학분야에서 하는 것은 물리학보다 좀 더 엄밀성을 추구하는 것 같지만요.)

    • snowall 2008.08.30 07:58 신고 EDIT/DEL

      다각형을 삼각형으로 나눈 선 위에 있는 점에 대한 논의는 본문에 되어 있구요
      오목다각형으로 삼각형으로 나눌 때, 만약 겹쳐짐이 생기거나 엉뚱한 영역이 삼각형에 포함되어 버리면 곤란합니다. 겹쳐짐이나 엉뚱한 영역의 포함 없이 잘 나누려면 볼록다각형으로 쪼갠 다음에 다시 삼각형으로 나누는 것이 좋겠죠.
      눈으로 보면 뻔한 것들이더라도 컴퓨터한테 시킬 때는 어떻게 될지 모르기 때문에, 완벽한 증명이 없는 한 가장 안전한 길로 가는 게 좋습니다.
      오목다각형을 여러개의 삼각형으로 단숨에 잘라주는 알고리즘은 생각나질 않아서 말이죠.
      그리고 수학이든 물리학이든 엄밀성을 추구하는 것은 마찬가지입니다. 그것이 어느 수준에서의 엄밀성이냐가 다르죠. 수학은 근거할 곳이 오직 공리와 논리밖에 없기 때문에 좀 더 추상적으로 엄밀하고, 물리학은 그 외에 실험에도 근거할 수 있기 때문에 덜 추상적일 뿐이라고 생각합니다.

    • goldenbug 2008.08.30 09:38 신고 EDIT/DEL

      물리학은 수학에서 사용하지 않는 (엄밀히 증명되지 않은) 수학적 공리(?)를 그대로 사용하는 경향이 있죠. ^^

    • snowall 2008.08.30 17:58 신고 EDIT/DEL

      공리(Axioms)는 증명하지 않고 사용하는 것들이므로 물리학이든 수학이든 별 문제는 없습니다.
      정리(Theorems)는, 물리학의 경우에는 수학적인 증명은 하지 않는 경우도 있습니다. 그러나, 그 경우에도 실험적인 근거는 갖고서 사용하는 것이기 때문에 증명되지 않은 것은 아닙니다.