ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 다각형과 점 위치 구하기
    알고리즘 2009.01.09 17:31

    삼각형 넓이 구하기 (http://lsujang.egloos.com/845237)

    3차원 좌표공간에서의 벡터 외적을 이용하면 쉽게 계산할 수 있다.
    먼저 벡터의 외적이란 두 벡터에 수직인 법선 벡터를 구하는 벡터 곱이다.


     위 그림에서 보면 a 벡터와 b 벡터를 외적하면 a X b(파란색) 법선 벡터가 구해진다. 이 외적의 결과값인 법선 벡터의 크기는 a 벡터와 b 벡터로 만들어지는 평행사변형의 넓이와 같다. 결국 법선 벡터의 크기를 2로 나누면 a 벡터와 b 벡터로 만들어지는 삼각형의 넓이를 구할 수 있는 것이다.

    외적의 크기를 구하는 공식은 |a||b|sinθ 이기 때문에 결국 평행사변형의 넓이를 구하는 공식과 같게 된다.
    (|a|a 벡터의 크기(길이)를 나타내고 sqrt(a.x^2 + a.y.y^2) 계산으로 구한다.)

     



    다각형 안에 점의 존재여부 판단(http://lsujang.egloos.com/845586)

    벡터의 외적을 이용하면 3개의 점(A, B, C)이 이루는 삼각형 안에 또다른 점 D가 포함되어 있는지의 여부를 손쉽게 판단할 수 있다. 바로 곱하여지는 두 벡터의 위치에 따라 법선 벡터의 방향이 달라진다는 성질을 이용한 것이다. 여기선 오른손 좌표계를 이용한다고 정하자.(머 왼손 좌표계라도 상관은 없다.)


    정리하자면 A X BB X A 의 방향이 서로 반대가 된다. ( A X B = - B X A )
    외적 값이 양수가 나오면 첫 번째 벡터의 왼쪽(counterclockwise)에 두 번째 벡터가 위치한다는 걸 의미한다.
    음수라면 그 반대가 된다.


    위 삼각형 그림에서 삼각형이 XY 2차원 평면상에 있다고 한다면, 외적값의 방향은 z좌표가 음수쪽에 있는지, 양수쪽에 있는지에 따라 결정된다. 따라서 전체 외적을 계산할 필요없이 z좌표만 계산하여 3개의 z좌표중 부호가 다른 값이 나온다면(좀 더 정확히 말해서 음의 부호값이 하나라도 있다면...) 해당 점은 삼각형 바깥쪽에 위치한다고 판단할 수 있다. 왼쪽 삼각형 경우를 보면 CA벡터의 오른쪽(colckwise)에 CD벡터가 위치하므로 방향이 음수가 나온다. 

    위 내용을 일반화 하면 삼각형 뿐만 아니라 어떠한 다각형 안에 점이 존재하는지 여부를 쉽게 판단할 수 있다.

    댓글 0

Designed by Tistory.