多角形塗りつぶし(1)

• 描画先における、図形の Y の描画範囲 Ymin, Ymax を求める
• Ymin〜Ymax の各 Y 位置において、多角形の各辺との交点 X をすべて求める
• すべての交点を値の小さい順に並び替える
• 各交点間で水平線塗りつぶしを行う
• 次の Y 位置へ...

X = x1 + (Y - y1) * (x2 - x1) / (y2 - y1)

#include "sptk.h"

#define WIDTH  300
#define HEIGHT 300

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

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

int get_intersection(int y,int *xlist,int maxcnt)
{
    int i,j,min_index,cnt,ntmp;
    SPTK_POINT pt1,pt2,pttmp;
        
    /* 交点リストを作る */
    
    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 が下方向になるように入れ替え */
        
        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;
        
        xlist[cnt++] = pt1.x + (y - pt1.y) * (pt2.x - pt1.x) / (pt2.y - pt1.y);
    }

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

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

    /* 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, xlist, 100);
        if(xcnt == -1) continue;
        
        /* 交点間を塗りつぶし */
        
        for(i = 0; i < xcnt; i += 2)
        {
            for(x = xlist[i]; x <= xlist[i + 1]; 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;
}