[태그:] Algorithm

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

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

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

IDW는 이미 알고 있는 값으로부터 알고자 하는 값을 보간하는 방법입니다. IDW를 사용하여 주어진 점 x에 대한 보간된 값 u를 결정하는 일반화된 형태의 보간 함수는 다음과 같습니다.

N은 이미 알고 있는 값의 개수, w는 가중치의 값, u는 앞서 말한 계산되어 나온 보간된 값입니다. IDW에서 중요한것은 가중치의 값에 해당되는 w에 대한 함수가 여러개 존재하며, Spepard 방식과 Liszka 방식 그리고 이들의 변종이 존재합니다. 여기서는 Spepard 방식에 대한 w값에 대해서만 살펴 보겠습니다.

위의 식이 Spepard님이 정의한 가중치 w의 값입니다. d는 보간하고자 하는 지점(x)와 이미 알고 있는 지점(xk) 사이의 공간적 거리입니다. 바로 거리(Distance)의 역(Inverse)에 대한 가중치(Weighting)라는 의미로 IDW가 된 것입니다.

p는 0보다 큰 실수값입니다. 이 p값의 범위에 따라 전체적인 보간된 양상이 다양하게 결정됩니다. p의 범위가 0~1이면 전체적인 양상이 좁고 날카로우며 1보다 크면 넓고 부드럽게 퍼져서 보간이 됩니다. 눈에 보이는 보간된 양상을 글로써 표현하려니 한계가 있는데… 이 부분에 대해서 실제 구현을 통해 살펴보도록 하겠습니다.

끝으로 IDW처럼, 이미 알고 있는 값을 통해 다른 값을 추정(보간)하는 방법 중 Kriging 기법이 있습니다. 기회가 닿는 다면 이 Kriging 기법에 대해서도 논의해 보고 싶습니다.