交点間の塗りつぶし規則
前回は多角形塗りつぶしをやりましたが、例えば以下のように、辺が交差するように頂点を指定した場合、中はすべて塗りつぶされず、交差した内側が空く状態になります。
これは、コードに問題があるのではなく、そういう形になるような規則で塗りつぶしているので、結果、そうなるというだけです。
実際にペイントソフトで使う場合は、中もすべて塗りつぶしたいという場合があるでしょう。
その場合は、求めた交点間を、別の規則で塗りつぶす必要があります。
これは、コードに問題があるのではなく、そういう形になるような規則で塗りつぶしているので、結果、そうなるというだけです。
実際にペイントソフトで使う場合は、中もすべて塗りつぶしたいという場合があるでしょう。
その場合は、求めた交点間を、別の規則で塗りつぶす必要があります。
やり方
前回は、交点の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 になった場合は塗りつぶさず、それ以外では塗りつぶすようにします。
この規則で交点間を塗りつぶしていくと、交差した部分の中身も塗りつぶすことができます。
今回は、この交点の座標はそのまま使うことにして、さらにその交点の元となった辺の上下方向をパラメータとして用意し、それを使うことで、交点間を塗りつぶすか否かを判断します。
例えば、上の図で、スキャンの 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
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 とします。
ただし、交点計算時には、Y 位置が常に下方向になるように値が入れ替えられているので、辺の 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として、辺の方向値を加算していきます。
そして、その値が0ならば、その交点間は塗りつぶしません。
値が0になる時というのは、例えば、+1 の次が -1 となる場合ですから、辺が上下に山なりになった後です。
こうして塗りつぶすと、多角形の中身はすべて塗りつぶされます。
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 となる場合ですから、辺が上下に山なりになった後です。
こうして塗りつぶすと、多角形の中身はすべて塗りつぶされます。