シンプルに画像に円を描画したい

ピクセル画像に単純な円を描画する方法についてまとめています. ここで紹介するものはブレゼンハムのアルゴリズムと同様な発想のMidpoint Circle Algorythmです.

線の描画に関しては右で記載しています. こちらはブレゼンハムのアルゴリズムです.

まず円の8分の一を考えます. 下の図のように半径をrとしたときに、(r,0)から円を書き始めて、 (r,r)になるまでピクセルを埋めていきます. このときにyは必ず1ずつ増えますが、xは0または1減らす(2以上だと線が途切れてしまう)ことがわかります. そのためxを増やさないままか1増やすかの選択を繰り返し、(r,r)になるまで点を打っていきます. 以上でアルゴリズムは完成です.とてもシンプルで実装も容易です.0のままか1を増やすかは、どちらがよりx^2+y^2=r^2の形に近くなるかで判定すればよいです.(rの近いほう) 平方根を行うと遅くなるので、平方根を使わないで比較をします.

次の点を0を減らすか維持するかを決めるにあたり、前回の座標が\((x_i,y_i)\)だったときに、どのような判定式になるかを計算します. rとx,yのユークリッド距離の誤差を与える関数をerrとして、\(y_i\)は常に1増やすことに注意すると $$err(x_i-1, y_i+1) < err(x_i, y_i+1)$$ のように記述することができます. この不等式を解いていくと最終的に、以下が導かれます. $$2err(x_i, u_i) + (2y_i+1) + (1-2x_i) >0$$ すなわち上記の式で判定を行えます.この数式においては、整数値の掛け算と足し算のみしか含まれないので、高速に判定を行うことができます.