原点を(X0,Y0)とする半径Rの真円を表す方程式は
(X - X0)2 + (Y - Y0)2 = R2
または
| X | = | Rcosθ + X0 |
| Y | = | Rsinθ + Y0 |
で示すことができるので、上式に適当な値を代入して座標を計算することによって円弧を描くことが可能となります。
しかし、この方法では実数演算が必要で処理が重くなるので、整数演算のみを使って円を描くアルゴリズムを検討していきます。
まず、円の8分の1(45度分)を描画することに限定して考えます。下図のように原点(0,0)を中心とする半径Rの8分円を点(R,0)から時計回りに描いていく場合円弧は必ず45°よりも急な傾きの曲線となるため、描画途中ある点P(X,Y)を描いた後次に描くべき点は
| 真下の点PV | (X,Y+1) |
| 左下の点PD | (X-1,Y+1) |
のいずれかになり、この2点のうち真の円に近い側を選択すればよいことになります。
点PV、PDのどちらが真の円弧に近いかを知るためには、それぞれの点について円周からの距離を求めてみればよいことになります。
点(X,Y)の原点からの距離は
sqrt(X2 + Y2) (sqrt()は平方根関数)
だから
D = sqrt(X2 + Y2) - R
により円からの距離Dが得られます(このときDの符号は点が円の内側にあるか外側にあるかを示します)。
わざわざ平方根をとって正確な距離を求める必要はないので、点(X,Y)から原点までの距離の平方と半径Rの平方との差をとって
E = X2 + Y2 - R2
にて比較を行うことにします。
まず、PV(X,Y+1)の誤差EVは
EV = X2 + (Y + 1)2 - R2
点P(X,Y)についての誤差Eを使って書き直せば
EV = E + 2Y + 1
となります。同様にPD(X-1,Y+1)の誤差EDを求めると
| ED | = | (X - 1)2 + (Y + 1)2 - R2 |
| = | E - 2X + 2Y + 2 |
となり、両者を比較して
| |EV| - |ED| < 0 | なら | 点PV、 |
| |EV| - |ED| > 0 | なら | 点PD |
を選択すればよいことになります。
ところで、不等式
|EV| - |ED| < 0
は
EV2 - ED2 < 0
と等価です。式の左辺を因数分解して
(EV + ED)(EV - ED) < 0 より
(2E - 2X + 4Y +3) (2X - 1) < 0
ここで半径R>0ならば必ずX≧1であるから(Xは必ず整数値であり、今描こうとしている8分円はY軸と交わらない)、両辺を2X-1で割って
2E - 2X + 4Y +3 < 0
よって左辺をFとしたとき、
| F < 0 | なら | PV |
| F > 0 | なら | PD |
を選択すればいいことになります。
このFは、Xが1減少したとき
| F(X-1,Y) - F(X,Y) | = | (2E(X-1,Y) - 2(X - 1) + 4Y + 3) - (2E(X,Y) - 2X + 4Y + 3) |
| = | 2((X - 1)2 + Y2 - R2) - 2(X2 + Y2 - R2) + 2 | |
| = | -4X + 4 |
増加し、Yが1増加すると
| F(X,Y+1) - F(X,Y) | = | (2E(X,Y+1) - 2X + 4(Y+1) + 3) - (2E(X,Y) - 2X + 4Y + 3) |
| = | 2(X2 + (Y + 1)2 - R2) - 2(X2 + Y2 - R2) + 4 | |
| = | 4Y + 6 |
増加するわけだから
| ・PV(X,Y+1)を採用したとき | F = F + (4Y + 6) |
| ・PD(X-1,Y+1)を採用したとき | F = F + (4Y + 6) - (4X - 4) |
というように採用した点に応じて変化量を加えていけば求めることができます。その初期値F0は座標値(Ｒ,0)のときで
F0 = -2R + 3
となります。
以上をまとめると、原点を中心とする半径Rの8分円を描くアルゴリズムは
| 1) | X = R,Y = 0,F = -2R + 3で初期化する |
| 2) | (X,Y)に点を打つ |
| 3) | F≧0であればX = X - 1、F = F - 4X |
| 4) | 無条件にY = Y + 1、F = F + 4Y + 2 |
| 5) | X≧Yなら2)に戻る |
さて、円はX軸、Y軸、直線Y=X、直線Y=-Xに対して対象な図形ですから、あとはこの点(X,Y)と同時に
(-X,Y), (X,-Y), (-X,-Y), (Y,X), (-Y,X), (Y,-X), (-Y,-X)
にも点を打てば円全体が完成します。また、中心座標を加えて平行移動させてやれば、任意の点を中心とする円弧が描けるようになります。
以上のアルゴリズムをＣ言語で書くと下のようになります。
/* 中心(x0,y0)とする半径rの真円を描く */
void circle( x0, y0, r, col )
int x0,y0,r,col;
{
int x,y,F;
x = r;
y = 0;
F = -2 * r + 3;
while ( x >= y ) {
PSET( x0 + x, y0 + y, col );
PSET( x0 - x, y0 + y, col );
PSET( x0 + x, y0 - y, col );
PSET( x0 - x, y0 - y, col );
PSET( x0 + y, y0 + x, col );
PSET( x0 - y, y0 + x, col );
PSET( x0 + y, y0 - x, col );
PSET( x0 - y, y0 - x, col );
if ( F >= 0 ) {
x--;
F -= 4 * x;
}
y++;
F += 4 * y + 2;
}
}
|