コンピュータで円を描く

中学生の頃の話

座標を指定すると点を描画できるパーソナルコンピュータで
円を描こうとしたのだが、自分が打てた点は、座標軸と交わる4点だけだった。
その後、事典などを見ながら、三角関数が使えることが何となく分かってきたものの
三角関数のうち何を使えばいいかも最初は分からなかった。
更に、障害になったのがラジアン単位。
BASIC言語で三角関数を使うには、度では駄目で、ラジアン単位で
与える必用があった。しかも自分の知識は、πって何というレベル。
ラジアン = ２π×度／360
当時の自分にはまだ、一周を360度ではなく、円周率の2倍で表現するという
概念はなかった。
使う側では、面倒な変換でしかないが、数学的には合理的なのだ。
当時は、まだ三角関数は三角関数表という本で調べる時代かな。
パーソナルコンピュータも、関数電卓も、ポケコンも出始めの頃。
円を描くのが難しい理由の一つは、y=axのようなXとYの関係式で表現できない事だ。
答えが2つあるものは、関数ではない。
実際に自分がたどり着いた方法は、角度を媒介変数として使用して、
X、Y座標を三角関数で求める方法だった。
また、円を好きな位置に描くには、加算による平行移動の概念が必用。
三角関数を描くのに、三角関数の値は、正規化されたものなので、
半径rの円を描くには、r倍する必用がある事なども理解する必用がある。

円の方程式を使う

r*r=x*x+y*y
から、以下を導く。
y=±√(r*r-x*x)
※ただし、定義域 : -r<=x<=r
計算をスマートに行うためには、円周を45度単位に分けて
数学的対称性を利用すると良い。
誤差も軽減できるのだがここでは割愛する。

【プログラム】

void drawCircle(int cx, int cy, int r) {
	for(int x=-r;x<r;x++) {
		double y = sqrt(r*r-x*x);
		int x2 = cx + x;
		int y2 = cy + y;
		int y3 = cy - y;
		plot(x2,y2);
		plot(x2,y3);
	}
}

半径=100

三角関数を使う

x = r * cosθ
y = r * sinθ
※ただし、ここでは定義域 : 0<=θ<2π とする。

【プログラム】

void drawCircle(int cx, int cy, int r) {
	for(int i=0;i<360;i++) {
		int x = cx + r * cos(i*3.14159/180);
		int y = cy + r * sin(i*3.14159/180);
		plot(x,y);
	}
}

半径=100

微分を使う

三角関数の微分には、
sinθ' = cosθ
cosθ' = -sinθ
のような関係がある。
これで円を描けと言われてあなたは描けるだろうか。
上の式では、どの角度でもこの関係が成り立つので、
角度θを意識する必用はない。つまり式から消去可能。
まず、半径は、正規化の概念で外して、単位円で考える事にする。
三角関数で円を描く式では、
cosθが X座標
sinθ がY座標
としたので
当てはめると
Y座標の速度 = X座標
X座標の速度 = -Y座標
※この場合の速度は、速度というよりグラフの傾き、X,Yの比率
　と考えるべきかもしれない。
単位円の円周を反時計回りに移動する点の速度のX成分とY成分が
得られるということだ。
ここでの速度は、1点での瞬間の速度だ。コンピュータ上で扱うには、
離散的に扱う必用がある。
若干誤差は出るが、一定時間動いたとして、その変位を求めることになる。
そこで、1回の移動を1/100に設定してみると。
x = x - y*0.01;
y = y + x*0.01;
となる。
ただ、これだけでは、何回ループさせれば円が1周するか分からない。
ほぼ足し算だけで円が描けてしまうなんて、小学生向き？

【プログラム】

void drawCircle(int cx, int cy, int r) {
	float x = r;
	float y = 0;
	for(int i=0;i<314*2;i++) {
		x = x - y * 0.01f; 
		y = y + x * 0.01f; 
		int x2 = cx + (int)x;
		int y2 = cy + (int)y;
		plot(x2,y2);
	}
}

半径=100

実際の問題点

こういうコンピュータ上で、何かやってみると、とりあえず出来たけれど
実用レベルではないという事が多い。
紹介した方法でも、小数点以下四捨五入した方が奇麗な円になる。
円の方程式では、X座標をもとにY座標を求めると、円の傾きによって
間隔が開いたり、誤差が大きくなってしまう不都合が生じる。
円を描くのに、三角関数で隙間が出来ないように描くには、
角度をどれくらいに設定すればいいか目安が分からない。
また、半径によってもその間隔は違って来る。
隙間が出来ないようにしても、同じ点を2回打つ無駄とか、
見た目にジャギジャギして奇麗でないという問題も残る。
だから、実際には、これらの方法は使われない。

実用アルゴリズム

実用的な円描画は、直線の描画で使われる、DDA(Degital Differential Analyser)
といった手法が取られる。
連続した直線、曲線を隙間無く描画するには、XかYの移動量が少ない方が
1ドット進むとき他方が何ドット進むかを求めて描画すれば良い。
円の描画では、
ブレゼンハム(Bresenham)、ミッチェナー(Michener) のアルゴリズムが有名。