오다기리 박의 알고리즘 노트

우리가 흔히 말하는 폴리곤은 N개의 점을 가진 도형을 말한다. 그래픽스 또는 CAD에서 N개의 좌표로 폴리곤을 쉽게 표현할 수 있다. 하지만 이러한 명시적인(explicit) 표현법 말고 암시적인(implicit) 표현법을 사용할 때도 있다. 그 중에 하나가 평면 기반 표현법이다. 평면 기반 폴리곤 표현법은 convex한 폴리곤을 평면 s 위에서 경계 평면 { bi } i∈Zn 으로 둘러쌓인 영역으로 표현한다는 것이다. (경계 평면은 반시계 방향 순서이다.) 아래 그림에서는 폴리곤이 포함된 평면 s와 각 에지를 포함하면서 s에 직교하는 평면 5개를 나타낸다. 이렇게 되면 폴리곤의 각 점은 vi = (s, bi-1, bi) 로 표현할 수 있다. 즉 각 점을 세 평면의 조합으로 표현 가능하다. 그리고 점의 ..