円を描く

(1)円弧描画のアルゴリズム

原点を( X0, Y0 )とする半径Rの真円を表す方程式は

( X - X0 )2 + ( Y - Y0 )2 = R2

または

X=Rcosθ + X0
Y=Rsinθ + Y0

で示すことができるので、上式を使って座標を計算することによって円弧を描くことが可能となります。
しかし、この方法では実数演算が必要になるので、整数演算のみを使って円を描くアルゴリズムを検討していきます。

まず、円の 1/8(45度分)を描画することに限定して考えます。下図のように、原点(0,0)を中心とする半径 Rの八分円を点(R,0)から時計回りに描いていく場合、円弧は必ず 45度よりも急な傾きの曲線となるため、ある点 P(X,Y)を描いた後、次に描くべき点は

真下の点PV( X, Y + 1 )
左下の点PD( X - 1, Y + 1 )

のいずれかになり、この二点のうち、真の円に近い側を選択することになります。

fig2-1-1

点PV、PDのどちらが真の円弧に近いかを知るためには、それぞれの点について円周からの距離を求めてみればよいことになります。
点( X, Y )の原点からの距離は

( X2 + Y2 )1/2

だから、

D = ( X2 + Y2 )1/2 - R

により円周からの距離 Dが得られます(このとき Dの符号は、点が円の内側にあるか外側にあるかを示します)。
しかし、点PV、PDそれぞれの値 Dを比較するためにわざわざ平方根を計算して正確な距離を求める必要はないので、点(X,Y)から原点までの距離の平方と、半径 Rの平方との差を誤差 Eとして

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は必ず整数値であり、今描こうとしている八分円は 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は座標値( R, 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に戻る

<Caution!!> Fを更新する式が上述のものと異なるのは、先に X, Yの値を増減しているからです。

ところで、円は X軸、Y軸、直線 Y = X、直線 Y = -Xに対して対象な図形だから、あとは描画対称の点(X,Y)といっしょに

( -X, Y ), ( X, -Y ), ( -X, -Y ), ( Y, X ), ( -Y, X ), ( Y, -X ), ( -Y, -X )

にも点を打てば円全体が完成します。また、中心座標を加えて平行移動させてやれば、任意の点を中心とする円弧が描けるようになります。

以下に、円弧描画のサンプル・プログラムを示します。

/* 点描画用関数 */
void pset( int x, int y, unsigned int col )
{
  :
}

/* 中心(x0,y0)とする半径rの真円を描く */
void circle( int x0, int y0, int r, unsigned int col )
{
  int x = r;
  int y = 0;
  int 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;
  }
}
[Go Back]前に戻る [Back to HOME]タイトルに戻る
inserted by FC2 system