[GIS] Sutherland-Hodgman Polygon Clipping 알고리즘

하나의 매우 큰 폴리곤의 일부를 화면상에서 확대할 경우에 렌더링 속도가 매우 느려질 수 있습니다. 예를 들어 한반도 전역을 아우르는 큰 하천 수계를 하나의 폴리곤으로 구성되어 있을 경우에.. 이 폴리곤을 화면상에 모두 그려지도록 할 경우 렌더링 속도에는 큰 문제가 없으나 이를 점차적으로 확대해 갈수록 그리기 속도는 점점 더… 그리고 훨씬 느려지게 됩니다.

이런 현상을 막기 위한 가장 좋은 방법은 화면 밖으로 벗어나는 대부분의 폴리곤 영역을 날려 버리는 것입니다. 바로 이때 적용할 수 있는 효율적인 알고리즘이 Sutherland-Hodgman Polygon Clipping 알고리즘입니다.

아래의 그림을 살펴보면 사각형 영역의 폴리곤과 잘려나갈 폴리곤이 존재합니다. 사각형 영역의 폴리곤은 모니터 영역이라고 생각하면 이 알고리즘을 실제 지도 엔진단에 적용할 때 이해가 쉽겠습니다.

사용자 삽입 이미지
위의 상황에서 Sutherland-Hodgman Polygon Clipping을 적용한 결과는 아래와 같습니다.

사용자 삽입 이미지
여기서 주의할 점은.. 이 알고리즘은 단지 폴리곤 렌더링에 적용할만하다 라는 점입니다. 이외의 부분에 대해서는 다른 알고리즘을 적용하기 바랍니다. 그 이유를 간단히 살펴보면 하나의 폴리곤을 화면 사각형에 대해 클리핑할때 다수의 폴리곤으로 분할되는 경우가 많은데 Sutherland-Hodgman Polygon Clipping 알고리즘은 다수의 폴리곤으로 분할하지 못하고 그 결과 역시 오직 하나의 폴리곤으로 클리핑하게 됩니다. 하지만… 그리기 위한 기능에서만큼은 그 어떠한 클리핑 알고리즘보다 빠른 퍼포먼스를 제공하므로 실제 적용할만한 알고리즘입니다.

이 알고리즘에 대한 소스 코드를 클래스화하여 제공합니다. 간단히 아래처럼 적용하면 원하는 결과를 얻을 수 있으리라 생각됩니다. 사용하는 좌표는 화면 좌표계입니다.

PolygonSHClipping clip;

// 폴리곤 구성(시작점과 끝점은 같아야 함)
clip.AddPoint(100, 100);
clip.AddPoint(200, 100);
clip.AddPoint(200, 200);
clip.AddPoint(100, 200);
clip.AddPoint(100, 100);

// 클리핑 사각영역 지정
clip.SetClippingWindow(0, 0, 150, 150);

// 클리핑
clip.Clip();

// 이후 클리핑된 영역을 그리기 위해서 다음 코드를 호출할 수 있다.
clip.DrawOutput(hdc);

이 소스 코드의 활용과 위의 이미지에 대한 대한 데모에 대한 전체 코드는 아래를 통해 다운로드 받을 수 있습니다. 마우스 왼쪽 버튼으로 폴리곤을 구성하고 오른쪽 버튼을 누르면 클리핑된 폴리곤이 화면상에 표시됩니다.

“[GIS] Sutherland-Hodgman Polygon Clipping 알고리즘”에 대한 4개의 댓글

  1. 아, 정말 큰 도움이 되는 글입니다. 그리기 위한 클리핑 알고리즘이 있으면 좋겠다. 라고 막연하게 생각한 하였는데, 이리도 구현까지 해두셨네요. 고민하다가 일정에 쫒겨 머신 사양에만 책임을 떠넘기던 저와는 정 반대십니다.
    말씀하셨던데로, 전국 100m 등고폴리곤을 아주 작은영역을 그릴때, 기존에 사용하던 클리핑모듈을 사용하면, 프로세스 시간은 그렇다 치더라도, 오버플로우까지 발생되어, 난감한 경우가 한두번이 아니였거든요.

    1. 저와 동일한 이유로 클리핑 알고리즘이 필요하셨군요. 저 역시 처음엔 미루다가.. 도저히 밀룰게 못되어 결국 이 알고리즘을 적용하게 되었답니다.

  2. 하나의 매우 큰 폴리곤을 한 화면에 모두 보이게 하는 경우에 렌더링 속도가 괜찮다고 하셨는데,,, 일반적인 경우와 반대의 말씀이 아닌가요? 잘 이해가 안갑니다..

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다