直線の描画(アルゴリズム)

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

下の関数は、割算と掛算を引算と足算に変形するものです。SetPixel()関数は、VRAMにドットを設定する処理です。

void DrawLine(int x1, int y1, int x2, int y2)
{
    int W = x2 - x1;
    int H = y2 - y1;
    int dx = 0;
    int dy = 0;
    int Wy = 0;
    int Hx = 0;
    if (W >= H)
    {
        for (dx = 0; dx <= W; dx ++)
        {
            SetPixel(x1+dx, y1+dy);
            Hx += H;
            if (Wy < Hx)
            {
                Wy += W;
                dy += 1;
            }
        }
    }
    else
    {
        for (dy = 0; dy <= H; dy ++)
        {
            SetPixel(x1+dx, y1+dy);
            Wy += W;
            if (Hx < Wy)
            {
                Hx += H;
                dx += 1;
            }
        }
    }
}