satoh

知っているようで知らないデジタル図形処理 ~任意形状図形の選択から交点・接点・接線計算まで、方程式では解けないノウハウを紹介

   

円弧を描いてみよう

今更、円弧を描く?

今ここには画面に点を打つだけのサービス(API)しか用意されていないグラフィックスライブラリがあると考えてください。
さあ、どうやって円を描く?どうやって円弧を描く?
……もうこんな機会はないかもしれません。
しかしそのおかげでデジタル処理で円弧(円も)を描くしくみに出会うことがなくなっています。これから一体、誰がこういった技術を継承していくのでしょうね…
それはさておき、今回はデジタル処理で円弧(円)を描くにはどうするか考えてみます。
円弧(円)を描くのはデジタルで処理する場合、三角関数は全く使いません。プレゼンハムのアルゴリズムをちょっとだけ拡張して描きます。ミッチェナーの方法なども有名です。
ポイントは、円を1/8ずつ描くことにあります。X,Y座標は±とXとYの入替を考えれば。次に打つべき点の計算は円周分全部行う必要はありません。1/8部分だけ計算すれば、残りの部分は、符号入替とXY入替で求められることになります。次の点の計算は、点を打ちながら本来の円から外れないように加減していく単純なものとなります。
文頭で少し嘆いては見ましたが、こうしたアルゴリズムについては結構ネット上に紹介があります。(参考1参考2参考3

円ではなく円弧を描きたい

円を描くのは簡単です。
検索すれば実用的な円描画アルゴリズムがたくさん出てくるでしょう。前章で示した参考サイトでも十分なソースコードが提示されています。
ところが円弧となるといきなり面倒くさくなります。
私が考えたアルゴリズムは、基本はプレゼンハムのアルゴリズムで円を描画するものをメインとします。
これに、開始点と終了点の存在する象限(第1象限~第4象限)を探し、各象限において以下のような6パターンの場合分けをします。
この条件を見ながらプレゼンハムのアルゴリズムで円を描画しつつ、描画不要部分は点を打たない、とします。

開始点と終了点が別の象限にある場合

以下のような円弧の場合です。

円弧-開始点と終了点が別の象限にある場合このとき、
・全く描かれない象限を0
・開始点が存在する象限を2
・終了点が存在する象限を3
・全部描画する象限を1
とします。

円弧-開始点と終了点が同一象限にある場合(小円)

以下のような円弧の場合です。
円弧-開始点と終了点が同一象限にある場合(小円)
このとき、
・全く描かれない象限を0
・開始点終了点が存在する象限を5
とします。

円弧-開始点と終了点が同一象限にある場合(大円)

以下のような円弧の場合です。
円弧-開始点と終了点が同一象限にある場合(大円) このとき、
・開始点終了点が存在する象限を4
・全部描画する象限を1
とします。

プログラム

では早速プログラムを書いてみます。
点を打つ関数を、仮に、

    void grPutPixel(int x, int y)

と定義してあります。
十分な高速性も考えて記述しています。

extern void grPutPixel(int x, int y) ;

//----------------------------------------------------------------------
//		中心点、半径、始点、終点指定で円弧を描く
//----------------------------------------------------------------------
void grArc(int cx, int cy, int r, int sx, int sy, int ex, int ey)
{
	int dx, dy, s ;
	int x1, y1, x2, y2, x3, y3, x4, y4 ;
	int psx, psy, pex, pey, ss, es, i, j ;
	unsigend int pass[4] ;

	psx = sx - cx ;
	pex = ex - cx ;
	psy = sy - cy ;
	pey = ey - cy ;
								// 始点の象限
	if (psx >= 0) {
		if (psy >= 0) ss = 3 ;
		else          ss = 0 ;
	} else {
		if (psy >= 0) ss = 2 ;
		else          ss = 1 ;
	}
								// 終点の象限
	if (pex >= 0) {
		if (pey >= 0) es = 3 ;
		else          es = 0 ;
	} else {
		if (pey >= 0) es = 2 ;
		else          es = 1 ;
	}

	if (ss == es) {										// 始点終点の象限が同じ
		if (((psy <  0) && (psx >= pex)) ||
			((psy >= 0) && (psx <= pex))) {
			for (i = 0 ; i < 4 ; i++) pass[i] = 0 ;		// 小円( < 90 )
			pass[ss] = 5 ;
		} else {
			for (i = 0 ; i < 4 ; i++) pass[i] = 1 ;		// 大円( > 270 )
			pass[ss] = 4 ;
		}
	} else {
		for (i = 0 ; i < 4 ; i++) pass[i] = 0 ;
		j = ss ;
		for (i = 0 ; i < 4 ; i++) {
			pass[j] = 1 ;								// 全表示
			if (j == es) break ;
			++j ;
			if (j > 3) j = 0 ;
		}
		pass[ss] = 2 ;									// 始点のみ
		pass[es] = 3 ;									// 終点のみ
	}

	dx = r ;
	s = r ;
	dy = 0 ;

	x1 = x2 = x3 = x4 = cx ;
	y1 = y2 = y3 = y4 = cy ;
	x1 += dx ;
	x2 -= dx ;
	y3 += dx ;
	y4 -= dx ;

	while (dx >= dy) {
		unsigned int  flag ;

		flag = 0x00 ;
										// 第1象限
		switch (pass[0]) {
			default:
				break ;
			case    1:
				flag = 0x03 ;
				break ;
			case    2:
				if ((x1 <= sx) && (y2 <= sy)) flag |= 0x01 ;
				if ((x3 <= sx) && (y4 <= sy)) goto or2 ;
				break ;
			case    3:
				if ((x1 >= ex) && (y2 >= ey)) ++flag ;
				if ((x3 >= ex) && (y4 >= ey)) goto or2 ;
				break ;
			case    4:
				if (((x1 <= sx) || (x1 >= ex)) && ((y2 <= sy) || (y2 >= ey))) ++flag ;
				if (((x3 <= sx) || (x3 >= ex)) && ((y4 <= sy) || (y4 >= ey))) goto or2 ;
				break ;
			case    5:
				if ((x1 <= sx) && (x1 >= ex) && (y2 <= sy) && (y2 >= ey)) ++flag ;
				if ((x3 <= sx) && (x3 >= ex) && (y4 <= sy) && (y4 >= ey)) goto or2 ;
				break ;
		}
		goto next2 ;
or2:
		flag |= 0x02 ;
next2:
										// 第2象限
		switch (pass[1]) {
			default:
				break ;
			case    1:
				flag |= 0x0C ;
				break ;
			case    2:
				if ((x4 <= sx) && (y4 >= sy)) flag |= 0x04 ;
				if ((x2 <= sx) && (y2 >= sy)) goto or8 ;
				break ;
			case    3:
				if ((x4 >= ex) && (y4 <= ey)) flag |= 0x04 ;
				if ((x2 >= ex) && (y2 <= ey)) goto or8 ;
				break ;
			case    4:
				if (((x4 <= sx) || (x4 >= ex)) && ((y4 >= sy) || (y4 <= ey))) flag |= 0x04 ;
				if (((x2 <= sx) || (x2 >= ex)) && ((y2 >= sy) || (y2 <= ey))) goto or8 ;
				break ;
			case    5:
				if ((x4 <= sx) && (x4 >= ex) && (y4 >= sy) && (y4 <= ey)) flag |= 0x04 ;
				if ((x2 <= sx) && (x2 >= ex) && (y2 >= sy) && (y2 <= ey)) goto or8 ;
				break ;
		}
		goto next3 ;
or8:
		flag |= 0x08 ;
next3:
										// 第3象限
		switch (pass[2]) {
			default:
				break ;
			case    1:
				flag |= 0x30 ;
				break ;
			case    2:
				if ((x2 >= sx) && (y1 >= sy)) flag |= 0x10 ;
				if ((x4 >= sx) && (y3 >= sy)) goto or20 ;
				break ;
			case    3:
				if ((x2 <= ex) && (y1 <= ey)) flag |= 0x10 ;
				if ((x4 <= ex) && (y3 <= ey)) goto or20 ;
				break ;
			case    4:
				if (((x2 >= sx) || (x2 <= ex)) && ((y1 >= sy) || (y1 <= ey))) flag |= 0x10 ;
				if (((x4 >= sx) || (x4 <= ex)) && ((y3 >= sy) || (y3 <= ey))) goto or20 ;
				break ;
			case    5:
				if ((x2 >= sx) && (x2 <= ex) && (y1 >= sy) && (y1 <= ey)) flag |= 0x10 ;
				if ((x4 >= sx) && (x4 <= ex) && (y3 >= sy) && (y3 <= ey)) goto or20 ;
				break ;
		}
		goto next4 ;
or20:
		flag |= 0x20 ;
next4:
										// 第4象限
		switch (pass[3]) {
			default:
				break ;
			case    1:
				flag |= 0xC0 ;
				break ;
			case    2:
				if ((x3 >= sx) && (y3 <= sy)) flag |= 0x40 ;
				if ((x1 >= sx) && (y1 <= sy)) goto or80 ;
				break ;
			case    3:
				if ((x3 <= ex) && (y3 >= ey)) flag |= 0x40 ;
				if ((x1 <= ex) && (y1 >= ey)) goto or80 ;
				break ;
			case    4:
				if (((x3 >= sx) || (x3 <= ex)) && ((y3 <= sy) || (y3 >= ey))) flag |= 0x40 ;
				if (((x1 >= sx) || (x1 <= ex)) && ((y1 <= sy) || (y1 >= ey))) goto or80 ;
				break ;
			case    5:
				if ((x3 >= sx) && (x3 <= ex) && (y3 <= sy) && (y3 >= ey)) flag |= 0x40 ;
				if ((x1 >= sx) && (x1 <= ex) && (y1 <= sy) && (y1 >= ey)) goto or80 ;
				break ;
		}
		goto next_end ;
or80:
		flag |= 0x80 ;
next_end:
		if (flag & 0x01) grPutPixel(x1,y2) ;
		if (flag & 0x02) grPutPixel(x3,y4) ;
		if (flag & 0x04) grPutPixel(x4,y4) ;
		if (flag & 0x08) grPutPixel(x2,y2) ;
		if (flag & 0x10) grPutPixel(x2,y1) ;
		if (flag & 0x20) grPutPixel(x4,y3) ;
		if (flag & 0x40) grPutPixel(x3,y3) ;
		if (flag & 0x80) grPutPixel(x1,y1) ;

		s -= 2 * dy + 1 ;
		if (s < 0) {
			--dx ;
			--x1 ;
			++x2 ;
			--y3 ;
			++y4 ;
			s += 2 * dx ;
		}
		++dy ;
		++y1 ;
		--y2 ;
		++x3 ;
		--x4 ;
	}
}

 - C, アルゴリズム, 図形, 計算