Computer-graphics-circle-generation-algorithm
提供：Dev Guides
円生成アルゴリズム
画面に円を描くことは、線を描くことよりも少し複雑です。 円を生成するための2つの一般的なアルゴリズム- Bresenham’s Algorithm および Midpoint Circle Algorithm があります。 これらのアルゴリズムは、円を描くために必要な後続のポイントを決定するという考えに基づいています。 私たちはアルゴリズムを詳細に議論しましょう-
円の方程式は$ X ^ \ {2} + Y ^ \ {2} = r ^ \ {2}、$です。ここで、rは半径です。
ブレゼンハムのアルゴリズム
ラスターディスプレイに連続した円弧を表示することはできません。 代わりに、円弧を完成させるために最も近いピクセル位置を選択する必要があります。
次の図から、ピクセルを（X、Y）の場所に配置し、次のピクセルをどこに配置するかを決定する必要があることがわかります-N（X + 1、Y）またはS（X + 1、 Y-1）。
これは、決定パラメーター d によって決定できます。
- d ⇐ 0の場合、N（X + 1、Y）が次のピクセルとして選択されます。
- d> 0の場合、S（X + 1、Y-1）が次のピクセルとして選択されます。
アルゴリズム
- ステップ1 *-円と半径の中心の座標を取得し、それぞれx、y、Rに保存します。 P = 0およびQ = Rに設定します。
- ステップ2 *-決定パラメーターD = 3 – 2Rを設定します。
- ステップ3 *-P≤Qの間、ステップ8を繰り返します。
- ステップ4 *-円を描く（X、Y、P、Q）を呼び出します。
- ステップ5 *-Pの値を増やします。
- ステップ6 *-D <0の場合、D = D + 4P + 6。
- ステップ7 *-Else Set R = R-1、D = D + 4（P-Q）+ 10。
- ステップ8 *-円を描く（X、Y、P、Q）を呼び出します。
Draw Circle Method(X, Y, P, Q).
Call Putpixel (X + P, Y + Q).
Call Putpixel (X - P, Y + Q).
Call Putpixel (X + P, Y - Q).
Call Putpixel (X - P, Y - Q).
Call Putpixel (X + Q, Y + P).
Call Putpixel (X - Q, Y + P).
Call Putpixel (X + Q, Y - P).
Call Putpixel (X - Q, Y - P).中間点アルゴリズム
ステップ1 *-半径 *r と円の中心$（x _ \ {c、} y _ \ {c}）$を入力し、原点を中心とする円の円周上の最初の点を取得します。
(x0, y0) = (0, r)- ステップ2 *-決定パラメータの初期値を次のように計算します
$ P _ \ {0} $ = 5/4 – r（この方程式の簡略化については、以下の説明を参照してください。）
f(x, y) = x2 + y2 - r2 = 0
f(xi - 1/2 + e, yi + 1)
= (xi - 1/2 + e)2 + (yi + 1)2 - r2
= (xi- 1/2)2 + (yi + 1)2 - r2 + 2(xi - 1/2)e + e2
= f(xi - 1/2, yi + 1) + 2(xi - 1/2)e + e2 = 0Let di = f(xi - 1/2, yi + 1) = -2(xi - 1/2)e - e2
Thus,
If e < 0 then di > 0 so choose point S = (xi - 1, yi + 1).
di+1 = f(xi - 1 - 1/2, yi + 1 + 1) = ((xi - 1/2) - 1)2 + ((yi + 1) + 1)2 - r2
= di - 2(xi - 1) + 2(yi + 1) + 1
= di + 2(yi + 1 - xi + 1) + 1
If e >= 0 then di <= 0 so choose point T = (xi, yi + 1)
di+1 = f(xi - 1/2, yi + 1 + 1)
= di + 2yi+1 + 1
The initial value of di is
d0 = f(r - 1/2, 0 + 1) = (r - 1/2)2 + 12 - r2
= 5/4 - r {1-r can be used if r is an integer}
When point S = (xi - 1, yi + 1) is chosen then
di+1 = di + -2xi+1 + 2yi+1 + 1
When point T = (xi, yi + 1) is chosen then
di+1 = di + 2yi+1 + 1- ステップ3 *-K = 0で始まる各$ X _ \ {K} $位置で、次のテストを実行します-
If PK < 0 then next point on circle (0,0) is (XK+1,YK) and
PK+1 = PK + 2XK+1 + 1
Else
PK+1 = PK + 2XK+1 + 1 – 2YK+1
Where, 2XK+1 = 2XK+2 and 2YK+1 = 2YK-2.- ステップ4 *-他の7オクタントの対称点を決定します。
- ステップ5 *-各計算ピクセル位置（X、Y）を$（X _ \ {C、} Y _ \ {C}）$を中心とする円形パスに移動し、座標値をプロットします。
X = X + XC, Y = Y + YC- ステップ6 *-X> = Yになるまでステップ3から5を繰り返します。
