다각형 클리핑

다각형 클리핑 알고리즘(Polygon Clipping Algorithm)은 다각형으로 다른 다각형을 잘라내는 알고리즘입니다.

많이 사용하는 다각형 클리핑 알고리즘으로는 서덜랜드-호지맨 알고리즘(Sutherland-Hodgman Algorithm)으로

볼록 다각형으로 다른 단순 다각형을 잘라내는 알고리즘입니다.

볼록 다각형의 여러 반평면의 교집합을 구하는 것이 주원리로

앞서 계산 기하에서 배운 CCW를 이용하여 각 점이 평면의 어느 쪽에 속하는 지 확인하며

직선의 왼쪽에 있는 점들과 변이 직선을 가로지를 경우 변과 직선의 교차점 또한 포함 시키는 과정을 반복합니다.