はじめに
これはアルゴリズムの解説です。
計算機科学（コンピュータグラフィックス）の分野において円を描画するときの古い手法の一つだそうです。
原理
円は、
x^{2} + y^{2} = r^{2}
で表されます。
まず考えるのは、昔よく使われていたらしい手法としてある、線形化することで簡単にすることができる方法です。
しかしまだ使いません。
不等式にすることで円の元の数式を変形した
0 = x^{2} + y^{2} - r^{2}
を利用して簡単に消せないか考えます。
なんと両辺から r² を引くことで簡単に消せそうです。しかしこのままだと全部消えるだけなので、定数を足したいですね。
そしてこれはコンピュータグラフィックスです！！ なので、半径1マスの範囲に点を落とすことができればいいのです。
つまり、
(r - 0.5)^{2} ≤ x^{2} + y^{2} ≤ (r + 0.5)^{2}
ということです。（ほぼ同一な円と円の間を埋めるような感じ）
これで0 = x² + y² - r²を利用できそうですね。
展開して、
\begin{alignat}{3}
r^{2} - r + 0.25 & ≤ x^{2} + y^{2} && ≤ r^{2} + &r + 0.25\\
-r + 0.25 & ≤ x^{2} + y^{2} - r^{2} && ≤ &r + 0.25
\end{alignat}\\
r という大きな値があるので、1ドットにも影響できないような0.25は無視することにします。
※f(x,y)の関数がないと何もできないので、実は0 = x² + y² - r²を使っても初期値代入の時に簡単になるだけですが、いい指針にはなります。
\begin{alignat}{1}
-r &≤ x^{2} + y^{2} - r^{2} &≤ r\\
0 &≤ x^{2} + y^{2} - r^{2} + r &≤ 2r \tag{1}
\end{alignat}\\
※0を作ると比較が楽になります
これでそれっぽい不等式はできました。真ん中の数式を今度こそ線形化していきましょう。不等式なので無茶をしやすいです。
\begin{align}
&a_n = x^{2} + y^{2} - r^{2} + r &\\
&a_0 = r &\because x^{2} + y^{2} - r^{2} = 0
\end{align}
しかし線形化が難しそうなので、一回、 x の変形と y の変形それぞれで式を作っていきましょう。
描画する際は連続的なので、xかyを1ずつ変更させます。なので、その時の変化を追ってみましょう
※a_nにxやyが少ないから簡単になります
\begin{alignat}{1}
x：&a_x - a_{x-1} &= ((x^{2} + y^{2} - r^{2} + r) - ((x - 1)^{2} + y^{2} - r^{2} + r)\\
& &= 2x - 1\\
y：&a_y - a_{y-1} &= (x^{2} + y^{2} - r^{2} + r) - (x^{2} + (y - 1)^{2} - r^{2} + r)\\
& &= 2y - 1\\
\end{alignat}
※漸化式における1は大きすぎて無視なんてできません
完成したかに見えます。しかし、この漸化式たちでは例えばxを少しずつ増加させていったとして、2rを超えた※①とき、a_nの値を減らすことができません。なぜなら二つともx,yを増加させたときにa_nを増加させる方向性だからです。片方を調整する用にする必要があります。
xとyが対称性をもっていることはわかっているので、実際にプログラムを動作させるときにどちらを優先して行い、もう一つで調整するのかを決める必要がありますが、対称性があるからどちらでも変わらないのでxを優先させるとします。※失言
ここで言うのも何なのですが、①でせっかく0を作っているので、2rを超えるまで繰り返してその度に調整よりも、0より小さくなったら調整の方がスマートですよね？ ということで、a_xを徐々に減少させ、減少しきれなくなったらa_yで増加させることにしましょう。
ということで、
\begin{alignat}{1}
x：&a_x - a_{x+1} &= ((x^{2} + y^{2} - r^{2} + r) - ((x + 1)^{2} + y^{2} - r^{2} + r)\\
& &= -2x - 1\\
y：&a_y - a_{y-1} &= (x^{2} + y^{2} - r^{2} + r) - (x^{2} + (y - 1)^{2} - r^{2} + r)\\
& &= 2y - 1\\
\end{alignat}
これで、
x = 0, y = 0, a = rで開始…ってあれ？ 円上にいませんね。困りました。仕方ないので、(x,y)=(r,0)※θ = 0 で始めるように作り直しましょう。円はx軸について対象 & y軸について対称 & y=xについて対称 & y=-xについて対称というすごい図形なので、これらの、簡単に軸について反転することで得られる座標は計算しないことにしましょう。0 ≤ θ ≤ π/2を超えてしまうと、xが単調減少、yが単調増加という状態から変わってしまい、不等式は条件付けが必要になりとても面倒くさくなってしまうので致し方ありません。
※x軸について反転は(x,-y)、y軸について反転は(-x,y)、y=xについて反転は(y,x)、y=-xについて反転は(-y,-x)
ということで、反転を用いたりすると、0 ≤ θ ≤ π/4だけで良くなりました。
xが+、yが+、a_x が単調減少、a_yが単調増加ということを念頭に置いてもう一度漸化式を立てましょう。（前と同じですが）
\begin{alignat}{1}
x：&a_x - a_{x+1} &= ((x^{2} + y^{2} - r^{2} + r) - ((x + 1)^{2} + y^{2} - r^{2} + r)\\
& &= -2x - 1\\
y：&a_y - a_{y-1} &= (x^{2} + y^{2} - r^{2} + r) - (x^{2} + (y - 1)^{2} - r^{2} + r)\\
& &= 2y - 1\\
\end{alignat}
ここでもう一度深く考えてみます。
0 ≤ θ ≤ π/4のように円を描くということはyの増加ばかりで、xはちっとも減少しません。つまり、メインはyにする必要があるので、失敗します。a_yがいくら毎回一回ずつ頑張ってもマイナスを取り戻せないのでひし形のようになると思います。
よって、プログラムのa_xとa_yの位置を逆にします、と言いたいですが、メインは負である必要があるので、漸化式も直しましょう。
xが+、yが+、a_x が単調増加、a_yが単調減少ということを念頭に置いてまた一度漸化式を立てます。
\begin{alignat}{1}
x：&a_x - a_{x-1} &= ((x^{2} + y^{2} - r^{2} + r) - ((x - 1)^{2} + y^{2} - r^{2} + r)\\
& &= 2x - 1\\
y：&a_y - a_{y+1} &= (x^{2} + y^{2} - r^{2} + r) - (x^{2} + (y + 1)^{2} - r^{2} + r)\\
& &= -2y - 1\\
\end{alignat}
終了θ=π/4ですが、x ≤ yになったら終了ですね。（グラフを思い浮かべると分かる）
x=yも描く場合（点が重なってしまう）はx < yですね。
最初の座標も描く場合（上同）はx < yにした上で描画部分を手前に移動ですね。
できました！！
まとめ
まとめてみると、
x = r, y = 0, a = r
while (x ≥ y) {
a = a - 2 * y - 1 # aの漸化式をxより先に動かします。
y = y + 1
if (a < 0)
a = a + 2 * x - 1 # 上同
x = x - 1
paint ( ( x, y ), ( x, -y ), ( -x, -y ), ( -x, y ), ( y, x ), ( y, -x ), ( -y, -x ), ( -y, x ) )
}
といった感じですね。
おっと、掛け算をなくすのを忘れていました。
x = r, y = 0, a = r
while (x ≥ y) {
a = a - y - y - 1 # aの漸化式をxより先に動かします。
y = y + 1
if (a < 0)
a = a + x + x - 1 # 上同
x = x - 1
paint ( ( x, y ), ( x, -y ), ( -x, -y ), ( -x, y ), ( y, x ), ( y, -x ), ( -y, -x ), ( -y, x ) )
}
といった感じですね。※-yなどは0-yでできます
誤差を減らす場合はa = r - 0.25で始めるとほんっの少しだけ減らせたりしません。まずこれほどの誤差が関わってくること自体ほぼないので。
実物