Cross Product Sign Method

삼각형의 각 변을 순회할 때, $P$가 모든 변의 같은 쪽에 있으면 내부에 있다.

“같은 쪽"을 판정하는 도구가 2D cross product의 부호다.

2D Cross Product

3D cross product에서 $z=0$일 때 $x$, $y$ 성분이 사라지고 $z$ 성분만 남는다.

$$ \vec{U} = (u_x,\; u_y,\; 0), \quad \vec{V} = (v_x,\; v_y,\; 0) $$$$ \vec{U} \times \vec{V} = (0,\; 0,\; u_x v_y - u_y v_x) $$

$z$ 성분 하나만 유의미하므로 스칼라처럼 사용한다.

이 $z$ 값의 부호가 $\vec{V}$가 $\vec{U}$의 어느 쪽에 있는지를 알려준다.

  • $\vec{U}$에서 $\vec{V}$로 반시계방향 회전 → $+Z$ 방향 → 양수
  • $\vec{U}$에서 $\vec{V}$로 시계방향 회전 → $-Z$ 방향 → 음수

삼각형에 적용

변의 방향 벡터 $\vec{U} = \overrightarrow{AB}$와 점까지의 벡터 $\vec{V} = \overrightarrow{AP}$의 cross product를 구한다. 세 변 모두에 대해 반복한다.

$$ d_1 = \overrightarrow{AB} \times \overrightarrow{AP} $$

$$ d_2 = \overrightarrow{BC} \times \overrightarrow{BP} $$

$$ d_3 = \overrightarrow{CA} \times \overrightarrow{CP} $$

$d_1$, $d_2$, $d_3$의 부호가 모두 같으면 $P$는 내부에 있다.

원리

CCW(반시계) 삼각형의 내부는 모든 변의 왼쪽이다.

  • 변 $\overrightarrow{AB}$: $P$는 왼쪽 (양수)
  • 변 $\overrightarrow{BC}$: $P$는 왼쪽 (양수)
  • 변 $\overrightarrow{CA}$: $P$는 왼쪽 (양수)

전부 양수 → 내부.

CW(시계) 삼각형이면 내부가 모든 변의 오른쪽이라 전부 음수가 된다. 어느 쪽이든 부호가 전부 같다 = 내부, 부호가 섞인다 = 외부.

따라서 winding order(CW/CCW)에 관계없이 동작한다.

구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

bool IsPointInTriangle(float px, float py,
                       float ax, float ay,
                       float bx, float by,
                       float cx, float cy)
{
    float d1 = (bx - ax) * (py - ay) - (by - ay) * (px - ax);
    float d2 = (cx - bx) * (py - by) - (cy - by) * (px - bx);
    float d3 = (ax - cx) * (py - cy) - (ay - cy) * (px - cx);

    bool hasNeg = (d1 < 0.0f) || (d2 < 0.0f) || (d3 < 0.0f);
    bool hasPos = (d1 > 0.0f) || (d2 > 0.0f) || (d3 > 0.0f);

    return !(hasNeg && hasPos);
}

hasNeg && hasPos가 true이면 부호가 섞여 있으므로 외부다. 그 반대가 내부.