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