Geometry & Recognition

내 점으로 만들어진 convex인 사변형에 어떤 점이 포함되어 있는지 않은지를 판별하는 문제는 프로그램을 하다 보면 종종 만나게 된다. 이보다 더 근본적인 문제는 주어진 점이 세 점으로 만들어진 삼각형의 내부점인가를 판단하는 것이다. 세 점이 주어지면, 시계방향이던, 아니면 반시계 방향이던, 한 방향으로 oriented 된 삼각형이 구성이 된다.  삼각형의 내부점들은 이 삼각형은 이루는 변(orientation 때문에 이 변들은 방향을 가지는 벡터임)에 대해서 모두 한쪽으로 치우쳐 상태가 된다. 이것을 수학적으로 표현하면, 삼각형의 세 변 벡터와 각각의 변 벡터의 시작점에서 주어진 점까지 선분이 만드는 벡터와의 외적의 부호가 동일한 값을 갖는다(삼각형의 CW나 CCW인 것에 상관없다)

$$\vec {A} =(A_x, A_y), ~\vec {B}=(B_x, B_y) ~\Longrightarrow ~\vec {A}\times\vec {B}=A_x B_y - A_y B_x$$

// 평면에서 두 벡터의 외적은 숫자를 준다; 3차원으로 생각할 때 z-성분이다. 
BOOL insideTriangle(POINT p, POINT A, POINT POINT B, POINT C) {
    ab = vec(A,B)와 vec(A,P)의 외적; 
    bc = vec(B,C)와 vec(B,P)의 외적; 
    ca = vec(C,A)와 vec(C,P)의 외적; 
    // 점이 변 위에 놓인 경우 외적이 0이 되므로 sign함수를 쓰는 경우 주의! 
    // return SIGN(ab) == SIGN(bc) && SIGN(bc) == SIGN(ca); 
    return (ab * bc >= 0) && (bc * ca >=0) && (ca * ab >= 0) 
}; 

(convex) 사변형은 항상 두 개의 삼각형으로 나누어지므로, 각각의 삼각형에 대해서 테스트하면 된다(이 방식이 직접적으로 4 변에 대해서 모두 다 같은 쪽에 치우쳐 있는가를 테스트하는 것보다 효과적이다. 삼각형을 이용하면 4 변에 대해서 다 테스트하지 않아도 중간에 결과를 얻을 수 있다. 물론, 주어진 사변형이 처음에 어떤 방향으로 orient 되었는지의 정보가 주어졌다면 훨씬 더 빨리 판별할 수 있는 방법이 있다).

// 점이 변 위에 있는 경우는 포함한다; 
// 사변형의 orientation에 무관하다(단, convex이어야 한다); 
BOOL insideQuadrilateral(POINT p, POINT A, POINT B, POINT C, POINT D) { 
    if (insideTriangle(p, A, B, D)) return TRUE; 
    else if (insideTriangle(p, B, C, D)) return TRUE; 
    return FALSE; 
}