[geometry]다각형 내부에 점이 있는가?

http://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle
소스 코드는 이곳에서 발췌 하였다.

기본 아이디어는 아래 그림에서 시작한다.

P0 이 P1과 P2직선 을 넘어서 존재하는지? 넘지 않는지? 를 따진다.
P0이 범위를 넘어서도 마찬가지다.

위 그림에서 파란색 영역이 더 크다면 P0은 직선을 넘지 않는다고 볼 수 있다.

(P0.x-P2.x)*(P0.y-P1.y) - (P0.x-P1.x)*(P0.y-P2.y)

위의 수식만 보고 어떻게 파란색과 빨간색영역을 구분하는지 의심이 들수도 있다.

위 수식은 양수/음수 둘중 하나만을 반환한다.

이제 삼각형을 생각해보자.

한 점이 모든 선에 대해 안쪽에 있으면 그건 그 점이 삼각형 내부에 포함된다는 뜻이다.

그러나 한 점이 모든 선에 대해 바깥쪽에 있을수는 없다.

그러므로, 파란색 빨간색이 중요한게 아니고, 모두 음수거나, 모두 양수거나 둘중 하나만 가능하므로

둘중 하나가 될경우 해당 점은 삼각형에 포함된다고 볼 수 있다.

P1과 P2 어느쪽의 x축을 먼저 기준으로 할지 생각해야 하므로 한쪽 방향으로 변을 순회하면서 검사만 하면 된다.

bool InOrOut(Point pt,Point line1,Point line2){
    return ((pt.x - line1.x)*(pt.y - line2.y) - (pt.x - line2.x)*(pt.y - line1.y))<0.0F;
}
bool PtInTriangle(Point pt,Point t1,Point t2,Point t3){
    bool b1,b2,b3;
    b1 = InOrOut(pt, t1, t2);
    b2 = InOrOut(pt, t2, t3);
    b3 = InOrOut(pt, t3, t1);
    return (b1 == b2) && (b2 == b3);
}
bool PtInRectangle(Point pt,Point t1,Point t2,Point t3,Point t4){
    bool b1,b2;
    b1=PtInTriangle(pt,t1,t2,t3);
    b2=PtInTriangle(pt,t1,t4,t3);
    return b1 | b2;
}