多角形塗りつぶし(2)・塗りつぶし規則

交点間の塗りつぶし規則
前回は多角形塗りつぶしをやりましたが、例えば以下のように、辺が交差するように頂点を指定した場合、中はすべて塗りつぶされず、交差した内側が空く状態になります。



これは、コードに問題があるのではなく、そういう形になるような規則で塗りつぶしているので、結果、そうなるというだけです。

実際にペイントソフトで使う場合は、中もすべて塗りつぶしたいという場合があるでしょう。
その場合は、求めた交点間を、別の規則で塗りつぶす必要があります。
やり方
前回は、交点の2つを一組として、偶数の位置から奇数の位置までを水平線で塗りつぶしていました。

今回は、この交点の座標はそのまま使うことにして、さらにその交点の元となった辺の上下方向をパラメータとして用意し、それを使うことで、交点間を塗りつぶすか否かを判断します。



例えば、上の図で、スキャンの Y 位置が点4と同じ位置だった場合、交点は、「辺 1-2、辺 2-3、辺 3-4、辺 4-5」の4つの交点が見つかります。
それぞれの交点を A,B,C,D とすると、「A-B 間、B-C 間、C-D 間」で、それぞれ塗りつぶすか塗りつぶさないかを判断できれば、交点2つを一組とする必要がなくなります。

そして、交点間を塗りつぶすか否かの判断に使うのが、辺の上下方向です。
交点と共に、その交点の元となった辺の上下方向 (上方向なら -1、下方向なら 1) を記録しておき、初期値を 0 として、交点が進むごとにその値を加算していき、値が 0 になった場合は塗りつぶさず、それ以外では塗りつぶすようにします。

この規則で交点間を塗りつぶしていくと、交差した部分の中身も塗りつぶすことができます。

ソースコード
ウィンドウ上の操作は、前回のコードと同じです。

032_fillpoly2.c
#include "sptk.h"

#define WIDTH  300
#define HEIGHT 300

typedef struct
{
    int x,dir;
}INTERSECTION;

SPTK_IMAGE *winimg;
SPTK_POINT pt[100];
int ptcnt = 0;

/** y 位置との交点リストを作成
 * return : 交点数 (-1 で処理なし) */

int get_intersection(int y,INTERSECTION *list,int maxcnt)
{
    int i,j,min_index,cnt,dir;
    SPTK_POINT pt1,pt2,pttmp;
    INTERSECTION istmp;
        
    /* 交点リストを作る */
    
    cnt = 0;

    for(i = 0; i < ptcnt; i++)
    {
        /* 辺の始点と終点 */
        
        pt1 = pt[i];
        pt2 = pt[(i + 1) % ptcnt];
                
        /* 水平線は除外 */
        
        if(pt1.y == pt2.y) continue;
        
        /* Y 位置が、現在の辺の終点と、次の辺の始点である場合、
         * 両辺が上方向、または下方向の場合は交点から除外 */
        
        if(y == pt2.y)
        {
            pttmp = pt[(i + 2) % ptcnt];
            
            if((pt2.y - pt1.y < 0 && pttmp.y - pt2.y < 0) ||
                (pt2.y - pt1.y > 0 && pttmp.y - pt2.y > 0))
                continue;
        }
        
        /* Y が下方向になるように入れ替え */
        
        dir = (pt2.y - pt1.y > 0)? 1: -1;

        if(pt1.y > pt2.y)
            pttmp = pt1, pt1 = pt2, pt2 = pttmp;

        /* Y の範囲外 */
        
        if(y < pt1.y || y > pt2.y) continue;
        
        /* 交点追加 */
        
        if(cnt >= maxcnt) return -1;
        
        list[cnt].x   = pt1.x + (y - pt1.y) * (pt2.x - pt1.x) / (pt2.y - pt1.y);
        list[cnt].dir = dir;
        
        cnt++;
    }

    if(cnt == 0) return -1;
    
    /* 小さい順に並べ替え */
    
    for(i = 0; i < cnt - 1; i++)
    {
        min_index = i;
    
        for(j = i + 1; j < cnt; j++)
        {
            if(list[j].x < list[min_index].x)
                min_index = j;
        }
        
        if(i != min_index)
        {
            istmp = list[i];
            list[i] = list[min_index];
            list[min_index] = istmp;
        }
    }
    
    return cnt;
}

void draw_fill_polygon()
{
    int ymin,ymax,i,x,y,xcnt,v;
    INTERSECTION list[100];

    /* Y の描画範囲 */
    
    ymin = ymax = pt[0].y;
    
    for(i = 1; i < ptcnt; i++)
    {
        if(pt[i].y < ymin) ymin = pt[i].y;
        if(pt[i].y > ymax) ymax = pt[i].y;
    }
    
    /* 各 Y 位置処理 */
    
    for(y = ymin; y <= ymax; y++)
    {
        xcnt = get_intersection(y, list, 100);
        if(xcnt == -1) continue;
        
        /* 交点間を塗りつぶし */
        
        v = 0;
        
        for(i = 0; i < xcnt - 1; i++)
        {
            v += list[i].dir;
            
            if(v == 0) continue;
        
            for(x = list[i].x; x <= list[i + 1].x; x++)
                sptk_image_setpixel(winimg, x, y, 0);
        }
    }
}

void winhandle(SPTK_EVENT *ev)
{
    switch(ev->type)
    {
        case SPTK_EVENT_BTTDOWN:
            if(!sptk_isgrab())
            {
                if(ev->mouse.btt == SPTK_MOUSEBTT_LEFT)
                {
                    if(ptcnt < 100)
                    {
                        pt[ptcnt].x = ev->mouse.x;
                        pt[ptcnt].y = ev->mouse.y;
                        ptcnt++;
                        
                        sptk_image_fillbox(winimg, ev->mouse.x - 1, ev->mouse.y - 1, 3, 3, 0xff0000);
                        sptk_update(NULL, ev->mouse.x - 1, ev->mouse.y - 1, 3, 3, 0);
                    }
                }
                else if(ev->mouse.btt == SPTK_MOUSEBTT_RIGHT)
                {
                    if(ptcnt >= 3)
                    {
                        sptk_image_clear(winimg, 0xffffff);
                        
                        draw_fill_polygon();
                        
                        sptk_update(NULL, 0, 0, WIDTH, HEIGHT, 0);
                        
                        ptcnt = 0;
                    }
                }
            }
            break;
        case SPTK_EVENT_WINDOW_CLOSE:
            sptk_quit();
            break;
    }
}

int main()
{
    sptk_init("test", WIDTH, HEIGHT);
    
    sptk_window_set_handle(winhandle);
    
    winimg = sptk_window_get_image();
    sptk_image_clear(winimg, 0xffffff);
    
    sptk_run();

    return 0;
}
解説
交点には、座標と共に辺の方向が必要なので、交点の値として INTERSECTION 構造体を作っています。

typedef struct
{
    int x,dir;
}INTERSECTION;
辺の方向を格納する
まずは、交点リスト作成時に、交点の X 座標と共に、現在の辺の Y 方向を格納します。
pt2.y - pt1.y > 0 で下方向なら 1、上方向なら -1 とします。

dir = (pt2.y - pt1.y > 0)? 1: -1;

list[cnt].x   = pt1.x + (y - pt1.y) * (pt2.x - pt1.x) / (pt2.y - pt1.y);
list[cnt].dir = dir;

ただし、交点計算時には、Y 位置が常に下方向になるように値が入れ替えられているので、辺の Y 方向は、値を入れ替える前に判定しておかなければいけません。
交点間の塗りつぶし
後は、辺の方向を判断材料として、交点間を塗りつぶしていきます。

v = 0;

for(i = 0; i < xcnt - 1; i++)
{
    v += list[i].dir;
    
    if(v == 0) continue;

    for(x = list[i].x; x <= list[i + 1].x; x++)
        sptk_image_setpixel(winimg, x, y, 0);
}

今回は、各交点においてそれぞれ、現在位置から次の位置までを、塗りつぶす範囲とします。

v に、初期値を0として、辺の方向値を加算していきます。
そして、その値が0ならば、その交点間は塗りつぶしません。

値が0になる時というのは、例えば、+1 の次が -1 となる場合ですから、辺が上下に山なりになった後です。

こうして塗りつぶすと、多角形の中身はすべて塗りつぶされます。