convex polygon 이든 concave polygon 이든 모든 다각형의 내부에서 점의 존재여부 판단

http://lsujang.egloos.com/845586

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

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

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

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

Convex polygon이든 Concave polygon이든 모든 다각형에 대한 판단 방법은 아래 링크를 참고.

http://www.alienryderflex.com/polygon/
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html