Graphics Programming
축 분리 정리(Separating Axis Theorem)의 간단한 증명 본문
축 분리 정리(분리축 정리)는 컴퓨터에서 두 볼록 물체의 교차 판정을 논할 때 흔히 언급되는 정리다. 두 물체를 투영한 구간(interval)이 겹치지 않는 축이 하나라도 존재한다면, 두 물체는 교차하지 않은 것이다. 간단한 그림을 몇 가지 그려보면 금방 그 의미를 알 수 있다.
인터넷에서 이 정리를 검색해보면 대부분은 바로 구현으로 넘어간다. "자, 이런 정리가 있어. 그러니까 우리가 앞으로 할 일은 각각의 모서리를 분리축으로 활용해서 투영을 하면 그 경우의 수가 MN + M + N가지고 시간복잡도는 이러쿵저러쿵..." 여기서 수학적인 부분을 확실하게 따져보자.
축 분리 정리를 간단하게 증명해보자. 두 볼록 도형 A, B가 교차할 때, 그 교집합을 ($ I = A \cap B \neq \phi $)이라 하자. 축 v에 도형 X를 투영한 결과를 Proj(X, v)라 할 때, 공집합이 아닌 도형을 어느 축에 투영하더라도 그 결과는 공집합이 아니다. 따라서 모든 v에 대해 ($ Proj(I, v) \neq \phi $) 이다. 여기까지를 이렇게 정리할 수 있다.
$$ I \neq \phi ~~\Rightarrow~~ \forall v, Proj(I, v) \neq \phi $$
단순히 이것의 대우를 취한다.
$$ \exists v, Proj(I, v) = \phi ~~\Rightarrow~~ I = \phi $$
풀어쓰면 이렇다. I를 투영한 결과가 공집합이 되는 축 v가 하나라도 존재한다면, I는 공집합이다. ($ I = A \cap B $)이고 ($ Proj(I, v) = Proj(A \cap B, v) = Proj(A, v) \cap Proj(B, v) $) 이며 더 풀어쓰면 다음과 같다. 임의의 축 v에 대해 A와 B를 각각 투영한 결과 교집합이 없다면, 원래의 도형 A와 B의 교집합도 없다. 즉 교차하지 않는다. 바로 축 분리 정리가 뜻하는 바이다. 증명 끝.
