交点間の塗りつぶし規則
前回は多角形塗りつぶしをやりましたが、例えば以下のように、辺が交差するように頂点を指定した場合、中はすべて塗りつぶされず、交差した内側が空く状態になります。
これは、コードに問題があるのではなく、そういう形になるような規則で塗りつぶしているので、結果、そうなるというだけです。
実際にペイントソフトで使う場合は、中もすべて塗りつぶしたいという場合があるでしょう。
その場合は、求めた交点間を、別の規則で塗りつぶす必要があります。
これは、コードに問題があるのではなく、そういう形になるような規則で塗りつぶしているので、結果、そうなるというだけです。
実際にペイントソフトで使う場合は、中もすべて塗りつぶしたいという場合があるでしょう。
その場合は、求めた交点間を、別の規則で塗りつぶす必要があります。
やり方
前回は、交点の２つを一組として、偶数の位置から奇数の位置までを水平線で塗りつぶしていました。
今回は、この交点の座標はそのまま使うことにして、さらにその交点の元となった辺の上下方向をパラメータとして用意し、それを使うことで、交点間を塗りつぶすか否かを判断します。
例えば、上の図で、スキャンの Y 位置が点４と同じ位置だった場合、交点は、「辺 1-2、辺 2-3、辺 3-4、辺 4-5」の４つの交点が見つかります。
それぞれの交点を A,B,C,D とすると、「A-B 間、B-C 間、C-D 間」で、それぞれ塗りつぶすか塗りつぶさないかを判断できれば、交点２つを一組とする必要がなくなります。
そして、交点間を塗りつぶすか否かの判断に使うのが、辺の上下方向です。
交点と共に、その交点の元となった辺の上下方向 (上方向なら -1、下方向なら 1) を記録しておき、初期値を 0 として、交点が進むごとにその値を加算していき、値が 0 になった場合は塗りつぶさず、それ以外では塗りつぶすようにします。
この規則で交点間を塗りつぶしていくと、交差した部分の中身も塗りつぶすことができます。
今回は、この交点の座標はそのまま使うことにして、さらにその交点の元となった辺の上下方向をパラメータとして用意し、それを使うことで、交点間を塗りつぶすか否かを判断します。
例えば、上の図で、スキャンの Y 位置が点４と同じ位置だった場合、交点は、「辺 1-2、辺 2-3、辺 3-4、辺 4-5」の４つの交点が見つかります。
それぞれの交点を A,B,C,D とすると、「A-B 間、B-C 間、C-D 間」で、それぞれ塗りつぶすか塗りつぶさないかを判断できれば、交点２つを一組とする必要がなくなります。
そして、交点間を塗りつぶすか否かの判断に使うのが、辺の上下方向です。
交点と共に、その交点の元となった辺の上下方向 (上方向なら -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 に、初期値を０として、辺の方向値を加算していきます。
そして、その値が０ならば、その交点間は塗りつぶしません。
値が０になる時というのは、例えば、+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 に、初期値を０として、辺の方向値を加算していきます。
そして、その値が０ならば、その交点間は塗りつぶしません。
値が０になる時というのは、例えば、+1 の次が -1 となる場合ですから、辺が上下に山なりになった後です。
こうして塗りつぶすと、多角形の中身はすべて塗りつぶされます。