円、楕円の描画(アルゴリズム)

ウィンドウズに描画関数（API）が沢山ありますので、円や楕円の描画ぐらいは、お話する必要がないかもしれません。マイコンや組み込み系の場合は、LCDに線や円などを描画する関数を自分で実装しなければならない時があります。円や楕円を描画する為に、描画しながら座標を計算することが必要です。普段、方程式から割算と掛算と平方根演算で座標を算出することができますが、割算命令と掛算命令のないマイコンの場合は、描画速度が遅くなります。なので、割算と掛算演算を使わずに円を描画するアルゴリズムが必要です。

下のソースは円を描画する関数は、x'=-y, y'=xという微分公式をうまく利用するものです。SetPixel()関数は、VRAMにドットを設定する処理です。xx / 128という処理は割算に見えますが、シフト命令（xx>>7）で実現できます。

処理時間を節約するために、円形の対称性を利用しています。円周上の座標を八分の一しか計算していません。

void DrawCircle(int cx, int cy, int r, CDC* pDC)
{
　　int xx = 128*r;
　　int yy = 0;
　　int x = 0;
　　int y = 0;
　　while (yy <= xx)
　　{
　　　　x = xx / 128;
　　　　y = yy / 128;
　　　　SetPixel(cx+x, cy+y);
　　　　SetPixel(cx-x, cy-y);
　　　　SetPixel(cx-x, cy+y);
　　　　SetPixel(cx+x, cy-y);
　　　　SetPixel(cx+y, cy+x);
　　　　SetPixel(cx-y, cy-x);
　　　　SetPixel(cx-y, cy+x);
　　　　SetPixel(cx+y, cy-x);
　　　　yy += xx / 128;
　　　　xx -= yy / 128;
　　}
}

下のソースは楕円を描画する関数です。x'=-y*a/b, y'=x*b/xという微分公式をうまく利用するもので平方根の処理を省けますが、割算と掛算の処理はやはり必要です。

処理時間を節約するために、楕円形の対称性を利用しています。楕円周上の座標を四分の一しか計算していません。

void DrawEllipse(int cx, int cy, int a, int b)
{
    int xx = a * 64;
    int yy = 0;
    int x = 0;
    int y = 0;

    while (xx >= 0)
    {
        x = xx / 64;
        y = yy / 64;
        SetPixel(cx+x, cy+y);
        SetPixel(cx-x, cy-y);
        SetPixel(cx-x, cy+y);
        SetPixel(cx+x, cy-y);
        yy += xx * b / a / 64;
        xx -= yy * a / b / 64;
    }
}