アルゴリズム : 円描画

画像を作ってるのですが、円描画のまともな方法が分かりません。

現在は、数学っぽいサイトを検索した所円の方程式は
r2乗 = X2乗 + Y2乗
と言うのが出てきたのでそれを元に作ってます。

具体的には、y軸に近い部分はx軸から。x軸に近い部分はy軸から描画を始め、
それそれ8回に分けて一つの円を描画しまてす。

イメージ的には rを定数とし、y軸の直下や真上付近ならx軸を一つづつずらし、yの値を求めます。
x軸の右側付近とかならy軸をずらします。
数学風に書くと
y ** 2 = (x + n) ** 2 + r ** 2
みたいなイメージです。(n = 何個目のドットを描画しているか。**はPerlなどでべき乗)。
これの平方根を求めて端数を四捨五入してます。
この方法だと軸から遠ざかると塗りつぶすドットが飛び飛びになるので8回(もしくは4回)の描画が必要です。



問題はまず、
それが一般的な方法かどうかと言う点です。8回に分けるもんだから処理が汚いです。
さらになぜか、円も汚いです。
いや理由はだいたい分かるんですけど、ドット数に少数点とかないから四捨五入とかしてます。
すると、どうもちゃんとした円にならないです。そこドットの描画一個ズレてるだろコレ？
おまえそれ、明らかに1ドットずらしたほうが綺麗な円になるぞ？
みたいことが起きます。


もう一つ、他の疑問なんですがちょっと数学的な疑問で、
円を1/8づつ描画させるにはnのループ回数を
n = r / (1.4140 < m < 1.4146) くらいの値に設定しなきゃならないことが分かりました。
なぜ割り算させたのかはもう覚えてません。
一つづつ手作業で確かめて絞り込んだ数値なのですが、
どうもmが2の平方根に似ている気がします。
なぜこうなるんでしょう。たぶん数学的な何かだと思うのですが。

なお数学的な知識は全然ないです。学校では一日中寝るのが特技でした。
まさかこんな技術が必要になるとは…。

No.1 ベストアンサー 回答者： ulisrt 回答日時： 2012/05/26 12:07

ミッチェナーの円の描画アルゴリズムというよく知られた手法があるので調べてみてください。

この回答への補足

ありがとうございました。
今まであった使ってた処理を整理して書き換えた所で納得がつきました。

選びにくいのですが最初の返信をベストアンサーの理由にしようと思います。

補足日時：2012/05/27 00:16

この回答へのお礼

ありがとうございます。
本日の昼に検索した所、出てきました。

すごく平たく言うと、基本の式は今のままで構わないが、
普通は1ドットずつ全部計算しないと言うことなのでしょうか。
そうなのでしょうね。

お礼日時：2012/05/26 19:59

No.5 回答者： ulisrt 回答日時： 2012/05/26 21:28

#1です。

おっしゃる通り、基本の式は同じです。

ミッチェナーのアルゴリズムの特徴の一つは、三角関数や絶対値の計算を使わず、整数の範囲で実現できるので比較的に高速です。

また、誤差がより小さい画素が選択されるので
> 1ドットずらしたほうが綺麗な円になるぞ？
ということが軽減されます。

ただし、やはり1/8円弧ずつ描くので、その点で処理が入り組んでしまうのは改善しませんけれども。

この回答へのお礼

よく見てよく理解して作ろうと思います。
ただ最近のPCは恐ろしく高性能なので、ある程度は処理(記述)のスマートさが優先になるかもしれません。

ありがとうございました。

お礼日時：2012/05/27 00:20

No.4 回答者： dscripty 回答日時： 2012/05/26 19:06

訂正

色々へんだった。。。

y = r * sinθ

θを -π/2～π/2 まで、幾つかに(3*r程度)分割して、順に y を求めて、

その y をしたの式にあてはめて、x を求める。

x^2 + y^2 = r^2

この回答へのお礼

ご丁寧訂正にありがとうございました。


-----------------------------------------------------

今気づいたのですが、私も書いた式が間違ってるのに今気づきました。
y ** 2 = (x + n) ** 2 + r ** 2
こんな式自分のプログラムのどこにも書いてなかったです。

お礼日時：2012/05/26 20:40

No.3 回答者： dscripty 回答日時： 2012/05/26 14:53

三角関数を使うといいよ！

x = r * sinθ

θを 0π～2π まで、幾つかに分割して、順に x を求めて、

その x をしたの式にあてはめて、y を求める。

x^2 + y^2 = r

θをなん分割するかだけど、

r * 6 ぐらいあれば十分。。。かな？

この回答への補足

回答頂いた皆様には申しわけないですが、
ベストアンサーをどうするかの判別が付かないので
自分が納得できる描画の処理を書けてから選びたいを所存でございます。

すみませんがお待ちください。

補足日時：2012/05/26 20:43

この回答へのお礼

ありがとうございます。
遠い昔に三角関数と言う言葉を聞いたような聞かないような記憶があります。
この計算法だと1ドットずつ出すと言うことでしょうか。

最初画像を作るとなった時、画像のフォーマットを知ればそれでOKと思ったんですが、
よくよく考えると何か描画すると言うのは全部2次元平面の数式が必要なんですね。
ナメてました。

rからループ回数を出すと言うのは塗りつぶすドット数の数を出すと言う解釈でいいですよね。
二乗とかなるとイメージが掴みにくいのですが。

お礼日時：2012/05/26 20:12

No.2 回答者： hashioogi 回答日時： 2012/05/26 13:27

ブレゼンハムのアルゴリズムという線分を描画するアルゴリズムがあります。

このアルゴリズムが成り立つ理屈を応用すると楕円を描画するアルゴリズムができます。
円は楕円の長辺と短辺を同じにしたものですから、この方法でも可能です。

この回答へのお礼

ありがとうございます。
こちらも見つける事ができました。

もう少ししっかり考えた上で記述を書き直そうかと思います。

お礼日時：2012/05/26 20:04