MFC를 써서 폴리곤의 내부를 칠하기 위해서는 윈도우  GDI region을 다루는  CRgn  클래스의 CRgn::CreatePolygonRgn() 메쏘드를 써서 해당 폴리곤으로 bound된 영역을 만든 이후에 CDC::FillRgn() 함수를 이용하여서 원하는 색으로 칠할 수 있다. 직접  raster에 칠하려고 할 때는 이러한 방법이 너무 불편하다 (물론 라스터(DIB)를 윈도우 비트맵으로 변환한 후에 위의 방법대로 칠하고, 다시 윈도우 비트맵을 라스터로 바꾸는 작업을 하면 되는데 번거롭다).

쉽게 생각할 수 있는 방법은  point_in_polygon()  방법을 써서 각각의 픽셀이 주어진 폴리곤 내부점인지를 확인하면서 작업을 할 수 있다. 그러나 이 방법은 한 픽셀을 검사하기 위해서 주어진 폴리곤의 모든 에지를 다 건들어야 하는 낭비를 하게 된다. 보다 효율적인 방법은 point_in_polygon 알고리즘을 구현할 때 사용하는 원리를 이용하면 적어도 한 스캔라인의 모든 픽셀에 대해서는 딱 한번만 전체 폴리곤의 에지를 검사하게 만들 수 있다. inclusion 테스트는 해당점에서 출발하는 수평반직선이 폴리곤과 몇번 교차하는지를 세서 내부점인지 외부점인지를 판별한다. 이것을 생각하면 수평선이 폴리곤과 교차하는 점들을 모두 구하여서(한번 폴리곤의 전체 에지검사가 필요) 크기의 순서대로 정렬할 때, 짝수번째 구간(0->1, 2->3,.....)에 들어가는 스캔라인의 픽셀들은 모두 폴리곤의 내부점이 된다는 것을 알 수 있다.

사용자 삽입 이미지

알고리즘 순서:
(1) 각각의 스캔라인에 대해서 교차점들을 구한다:
       꼭지점-i와 꼭지점-j(=i-1)를 잇는 직선의 방정식: x = x[i] + (x[j] - x[i])*(y - y[i]) / (y[j] - y[i]) 이므로
       현재의 scanline 위치에서 y값이 두 꼭지점의 y값 (y[i], y[j]) 사이에 있으면, 교차점의 x-좌표는 윗식의
       좌변값이 된다.
(2) 교차점들을 크기의 순서대로 정렬한다.
(3) 짝수번째 구간에 들어가는 스캔라인상의 픽셀들은 해당 색깔로 칠한다.

/*코드 샘플
** 폴리곤을 플로팅타입으로 변환이 필요?
*/
// qsort용 비교함수;
static int comp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
};
void FillPolygon(POINT poly[], int npoly,
                 DWORD color,
                 BYTE *image, int width, int height, int bpp)
{
    int *nodeX = new int [npoly] ; //never exceeds npoly;
    for (int y=0; y<height; y++)
    {
        // find intersection nodes;
        int nodes=0;
        for (int i=0, j=npoly-1; i<npoly; j = i++)
        {
            if (poly[i].y<y && poly[j].y>=y || poly[j].y< y && poly[i].y>= y)
            {//수평인 에지는 그리지 않는다(부등식을 자세히 보라)
                nodeX[nodes++] = (int)(poly[i].x +
                                double(y-poly[i].y)*double(poly[j].x-poly[i].x)/double(poly[j].y-poly[i].y) +.5);
                                //round to integer!!.
            }
        }
        // sort nodes (ascending order);
        qsort(nodeX, nodes, sizeof(int), comp) ;

        //  fill the pixels between node pairs.
        for (i=0; i<nodes; i+=2)
        {
            if   (nodeX[i  ]>=width) break;
            if   (nodeX[i+1]> 0 )
            {
                if (nodeX[i  ]< 0 ) nodeX[i  ]=0 ;
                if (nodeX[i+1]> width) nodeX[i+1]=width;
                for (int x=nodeX[i]; x<nodeX[i+1]; x++)
                    SetPixel(x, y, color, image, width, height, bpp); //다른 프로토타입을 가질 수 있다.
            }
        }
    }
    delete[] nodeX;
}

사용자 삽입 이미지

/**
** http://blog.naver.com/helloktk/80050645334 에서 옮김.
*/

'Computational Geometry' 카테고리의 다른 글

Polygon Triangulation (II)  (0) 2008.05.26
Polygon Triangulation  (4) 2008.05.25
Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Trapezoidalization  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요