영상처리에서 특정한 폴리곤의 내부에서의 픽셀 정보만 처리해야 하는 경우가 많이 있다. 이 경우에 폴리곤 내부영역의 마스크를 만들어서 사용하거나 $\tt inpoly(~)$ 함수를 호출하여서 그 폴리곤의 내부인지를 판별하는 방법을 사용할 수 있다. 가장 기본적인 폴리곤은 삼각형으로 여기서는 삼각형 내부를 색상 정보를 읽거나 칠할 때 필요한 알고리즘을 알아본다.

기본적으로 스캔라인에 기반한 처리를 해야 하므로, 각각의 스캔라인에 대해서 삼각형의 변과 교차하는 점을 찾아서 두 교차점 사이의 구간을 읽거나 색칠하면 된다. 삼각의 세 꼭짓점을  y값을 기준으로 정렬을 하면 삼각형은 그림의 (A)나 (B)의 경우로 나눌 수 있어서  이 작업이 보다 간단해진다.


아래의 코드는 이것을 구현한 것이다:

#define SWAP(a, b) {double t; t = (a); (a) = (b); (b) = t;}
void trifill(double x0, double y0, double x1, double y1, double x2, double y2) {
    //sort --> y0 < y1 <y2;
    if (y1 < y0) { SWAP(y0, y1); SWAP(x0, x1);}
    if (y2 < y0) { SWAP(y2, y0); SWAP(x2, x0);}
    if (y2 < y1) { SWAP(y1, y2); SWAP(x1, x2);}
    //now, y0 <= y1 <= y2 ;
    //calc dx/dy for edge(0->1), edge(0->2), edge(1->2);
    double d10, d20, d21 ;
    if (y1 - y0 > 0) d10 = (x1 - x0) / (y1 - y0);
    else   d10 = 0; //horizontal line;
    if (y2 - y0 > 0) d20 = (x2 - x0) / (y2 - y0);
    else d20 = 0;   //horizontal line;
    if (y2 - y1 > 0) d21 = (x2 - x1) / (y2 - y1);
    else d21 = 0;   //horizontal line;
    //
    double sx, ex, x;
    sx = ex = x0 ;
    double y = y0 ; //starting from (x0,y0);
    if (d10 > d20) {
        // 0->2->1 : counter clockwise;
        // 삼각형의 밑부분 스캔;
        // 각각의 수평스캔은 (0->2)변에서 출발하여서 (0->1)변에서 끝난다;
        // 따라서 y값의 끝은 y1이다 
        for (; y < y1; y++) {
            //현재위치 ;
            x = sx;  
            for ( ; x < ex ; x++) PutPixel(x, y);
            //다음 라인으로 이동;
            sx += d20 ; //시작점 ;
            ex += d10 ; //끝점 ;
        }
        // 삼각형의 윗부분 스캔 ;
        // 각각의 수평스캔은 (0->2변에서 출발하여서 (1->2)변에서 끝난다;
        // 따라서 y의 끝값은 y2이다;
        // 새로운 끝점의 시작은 (x1,y1);
        ex = x1; y = y1;
        for ( ; y <= y2; y++) {
            x = sx; 
            for( ; x < ex ; x++) PutPixel(x, y);
            //다음 라인으로 인동;
            sx += d20 ;
            ex += d21 ;
        }
    } else { 
        // 0->1->2 : counter clockwise;
        // 삼각형 밑부분 스캔;
        // (0->1)변에서 출발하여서 (0->2)변에서 끝난다;
        // 따라서 y값의 끝은 y1이다;
        for (; y < y1; y++) {
            x = sx;
            for (; x < ex; x++) PutPixel(x,y);
            sx += d10;
            ex += d20;
        }
        //삼각형의 윗부분 스캔 ;
        //각각의 수평스캔은 (1->2)변에서 출발하여서 (0->2)변에서 끝난다;
        //따라서 y의 끝값은 y2이다;
        //새로운 시작점의 시작은 (x1,y1);
        x = x1; y = y1;
        for (; y <= y2; y++) {
            x = sx;
            for(; x < ex; x++) PutPixel(x, y);
            sx += d21;
            ex += d20;
        }
    }
}'


삼각형 영역을 읽고 invert 시킨 경우:

728x90

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

Polyline Simplication  (0) 2010.01.17
한 점에서 선분까지 거리  (1) 2010.01.16
Triangulation을 이용한 Imge Effect  (0) 2009.12.18
Ellipse Drawing Algorithm  (0) 2008.06.04
Circle Drawing Algorithm  (1) 2008.06.03
Posted by helloktk
,

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. 짝수번째 구간에 들어가는 스캔라인상의 픽셀들은 해당 색깔로 칠한다.

static int comp(const void *a, const void *b);

더보기
// 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 (INT 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); 
                    //SetPixel()은 다른 프로토타입을 가질 수 있다.
            }
        }
    } 
    delete[] nodeX;
};

사용자 삽입 이미지

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

728x90

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

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