塗りつぶした多角形の描画

点を打つ関数pset()のみを使用して塗りつぶした多角形(ポリゴン)を描くプログラムを作成しました。基本となるアルゴリズム・プログラムは多角形の塗りつぶし1，多角形の塗りつぶし2を使わせてもらいました。グラフィックにはEGGX / ProCALLを使用しています。プログラムの作成はRaspberry Pi4で行っています。 

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include <eggx.h> /* EGGX を使う時に必要 */

/*
 * ポリゴンを構成する直線を表す構造体
 */
struct EDGBUF {
    double X;   /* 交点のX座標(初期値は始点のX座標) */
    int Y0;  /* 始点のY座標 */
    int Y1;  /* 終点のY座標 */
    double a;    /* 傾き(dX/dY) */
};

/************************** 
 * 頂点のリストより辺リストの作成する 
 * 引数　int dataN:頂点の数
 *      signed short int * ApexList;  頂点リスト
 *      struct EDGBUF * Edge;         辺リスト
 * 戻り値　辺リスト
 */
struct EDGBUF *GenerateEdgeList(int dataN,int *ApexList, struct EDGBUF *Edge )
{
    signed short int x,y;
    int i;

    for ( i = 0 ; i < dataN ; i++ ) {
        x = *( ApexList + 2 ) - *ApexList;
        ApexList++;
        y = *( ApexList + 2 ) - *ApexList;
        ApexList++;
        if ( y != 0 ) {
            Edge[i].X =  ( y > 0 ) ? * ( ApexList - 2 ) : *ApexList;
            Edge[i].Y0 = ( y > 0 ) ? * ( ApexList - 1 ) : * ( ApexList + 1);
            Edge[i].Y1 = ( y > 0 ) ? * ( ApexList + 1 ) : * ( ApexList - 1);
            Edge[i].a = (double) x /(double) y;
        }
    }
    return(Edge);
}

/***************************** 
 * X座標のソート(単純挿入法) 
 * 引数　struct EDGBUF *DataStart: 並び替えの先頭ポインタ
 *      struct EDGBUF *DataEnd:   並び替える最終ポインタ
 * 戻り値　なし
 */
void InsertSort(struct EDGBUF *DataStart,struct EDGBUF *DataEnd)
{
    struct EDGBUF *GetData, *DataAddr;
    struct EDGBUF p;

    for ( GetData = DataEnd - 1 ; GetData >= DataStart ; GetData-- ) {
        p = *GetData;
        for ( DataAddr = GetData + 1 ; ( *DataAddr ).X < p.X ; DataAddr++ )
            *( DataAddr - 1 ) = *DataAddr;
        *( DataAddr - 1 ) = p;
    }
}

/**************
 *  ポリゴン描画メインルーチン 
 * 引数 int StartEdge: 辺リストのスタートアドレス
 *     int EndEdge: 辺リストの終了アドレス
 *     struct EDGBUF *EdgBuf:  辺リストアドレス格納用配列
 * 戻り値　なし
 */
void PolyFill(int win,int StartEdge,int EndEdge,struct EDGBUF *EdgBuf)
{
    int ActiveEdgePointer, NonActiveEdgePointer;
    struct EDGBUF ep, eof;
    int x,y;
    int x0,x1;
    int MINY=0,MAXY=400; //画面のサイズY方向
    int MINX=0,MAXX=400; //画面のサイズx方向

    eof.X = 0x7FFFFFFF;

    /* 全ての辺リストを「未アクティブ」にする */
    //NonActiveEdgePointer = EdgBufPointer;
    for (int dp = StartEdge ;dp < EndEdge ;dp++ ) {
        EdgBuf[dp-StartEdge] = EdgBuf[dp];
    }
    ActiveEdgePointer = NonActiveEdgePointer = EndEdge - StartEdge;
    /* 「アクティブ」な辺リストの末尾に番人を設ける(ソート時に必要) */
    EdgBuf[ActiveEdgePointer + 1 ] = eof;
    for ( y = MINY ; y <= MAXY ; y++ ) {
        /* yと始点が一致した「未アクティブ」な辺を「アクティブ」にする */
        for ( int i = 0 ; i <= NonActiveEdgePointer ; ) {
            if ( EdgBuf[i].Y0 == y ) {
                ep = EdgBuf[i];
                EdgBuf[i] = EdgBuf[NonActiveEdgePointer];
                EdgBuf[NonActiveEdgePointer--] = ep;
            } else i++;
        }

        /* ｙと終点が一致した「アクティブ」な辺を削除する */
        for ( int i = NonActiveEdgePointer + 1 ; i <= ActiveEdgePointer ; ) {
            if ( EdgBuf[i].Y1 == y ) {
                EdgBuf[i] = EdgBuf[ActiveEdgePointer];
                EdgBuf[ActiveEdgePointer--] = eof;
            } else i++;
        }

        /* 交点のソート */
        InsertSort( &EdgBuf[NonActiveEdgePointer + 1] , &EdgBuf[ActiveEdgePointer] );
        /* クリッピング・エリア外の交点をチェックしながらライン描画 */
        for ( int i = NonActiveEdgePointer + 1 ; i < ActiveEdgePointer ; i += 2 ) {
            x0 = EdgBuf[i].X;
            x1 = EdgBuf[i+1].X;
            if ( x1 < MINX || x0 > MAXX ) continue;
            if ( x0 < MINX ) x0 = MINX;
            if ( x1 > MAXX ) x1 = MAXX;
            for ( x = x0 ; x <= x1 ; x++ ) pset(win,x,y);
            /* X座標の更新 */
            EdgBuf[i].X += EdgBuf[i].a;
            EdgBuf[i+1].X += EdgBuf[i+1].a;
        }
    }
}

/**************
 *  ポリゴンを描画する 
 * 引数 int vnum: 頂点の数
 *     int *data: 頂点のリスト{ x0,y0,x1,y1,x2,y2...}
 * 戻り値　なし
 */
void polygonf(int win,int vnum,int *data)
{
    struct EDGBUF *buf;
    
    buf = (struct EDGBUF *)malloc(sizeof(struct EDGBUF)*(vnum));
    if(buf==NULL) {
        fprintf(stderr,"Memory allocation error\n");
        exit(EXIT_FAILURE);
    }
    GenerateEdgeList(vnum,data,buf);
    PolyFill(win,0,vnum-1,buf);
    free(buf);
}

int main(int argc, char **argv)
{
    int win;
    int data[]={10,10,300,50,300,300,350,350,150,300,350,200,10,10};

    gsetinitialattributes(DISABLE, BOTTOM_LEFT_ORIGIN); /*eggxの座標設定を通常のグラフィックスと同じに*/
    win = gopen(400,400); /* 400x400 ピクセルのグラフィックス用ウィンドゥを開く */
    //layer(win,0,1);
    newrgbcolor(win,255,0,0);

    polygonf(win,7,data);

    newrgbcolor(win,0,0,200);
    drawline(win,0,400,800,400);
    drawline(win,400,0,400,800);
    //copylayer(win,1,0);
    ggetch(); /* キー入力があるまで待つ */
    gclose(win); /* グラフィックス用ウィンドゥを閉じる */
}

実行結果

参考

多角形の塗りつぶし1

多角形の塗りつぶし2

多角形の塗りつぶし　(1) ソリッド・エリア・スキャン・コンバージョン

多角形の塗りつぶし　(2) スキャン・ラインとの交点算出

多角形の塗りつぶし　(3) その他の手法

閉領域内部の塗りつぶし方 ＋ 曲線の描画法（ラスタライズ）

EGGX / ProCALL X11 Graphics Library since 1999