영상처리에서 특정한 폴리곤의 내부에서의 필셀정보만 처리해야하는 경우가 많이 있다. 이 경우에 폴리곤 내부영역의 마스크를 만들어서 사용하거나 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