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

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


아래의 코드는 이것을 구현한 것이다:
void trifill(double x0, double y0,
             double x1, double y1,
             double x2, double y2)
{
    //sort --> y0 < y1 <y2;
    if(y1 < y0) { double t = y0; y0 = y1; y1 = t; t = x0; x0 = x1; x1 = t;}
    if(y2 < y0) { double t = y0; y0 = y2; y2 = t; t = x0; x0 = x2; x2 = t;}
    if(y2 < y1) { double t = y1; y1 = y2; y2 = t; t = x1; x1 = x2; x2 = t;}
    //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;
    double 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 시킨 경우:

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

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

댓글을 달아 주세요