ブレゼンハムアルゴリズム

ブレゼンハム（bresenham）というアルゴリズムを使ってタイル環境で直線を描画するサンプルです。ブレゼンハムはペイントソフトの直線描画にも使われているそうです。ペイントの直線描画と同じようにドラッグすれば直線が引けます。

ブレゼンハムアルゴリズムのコードは下のようになります。引数のstartは直線の始点、endは終点です。インスタンス変数のlineに直線を構成するピクセルの座標が入ります。lineは戻り値にしてもいいと思います。

    /**
     * ブレゼンハムアルゴリズムで直線を引く
     * 
     * @param start 直線の始点
     * @param end 直線の終点
     */
    private void buildLine(Point start, Point end) {
        int nextX = start.x;
        int nextY = start.y;
        int deltaX = end.x - start.x;
        int deltaY = end.y - start.y;
        int stepX, stepY;
        int step;
        int fraction;

        for (step = 0; step < MAX_LINE_LENGTH; step++) {
            line[step] = null;
        }

        step = 0;

        if (deltaX < 0)
            stepX = -1;
        else
            stepX = 1;
        if (deltaY < 0)
            stepY = -1;
        else
            stepY = 1;

        deltaX = Math.abs(deltaX * 2);
        deltaY = Math.abs(deltaY * 2);

        line[step] = new Point(nextX, nextY);
        step++;

        if (deltaX > deltaY) {
            fraction = deltaY - deltaX / 2;
            while (nextX != end.x) {
                if (fraction >= 0) {
                    nextY += stepY;
                    fraction -= deltaX;
                }
                nextX += stepX;
                fraction += deltaY;
                line[step] = new Point(nextX, nextY);
                step++;
            }
        } else {
            fraction = deltaX - deltaY / 2;
            while (nextY != end.y) {
                if (fraction >= 0) {
                    nextX += stepX;
                    fraction -= deltaY;
                }
                nextY += stepY;
                fraction += deltaX;
                line[step] = new Point(nextX, nextY);
                step++;
            }
        }
    }

実を言うとなぜこの処理で直線が引けるのか直感的には納得できてません・・・おっ本当に引けたって感じです。

デバッガを使って（または紙の上で）変数の内容を追ってみるとわかりますが、fractionがキーポイントになっています。fractionの値によってx方向に線をのばすかy方向に線をのばすかが調整されてます。

よくわからないのはdeltaXやdeltaYが参考文献では2倍されている点です。この2倍はなくてもきちんと動作したので何を意味してるのかわかりませんでした・・・わかった方はぜひ教えてください（ウシオダさんが教えてくれました。ありがとうございます。下の追記参照）。

まあとりあえず便利なのでそのまま使えればいいかな。

ブレゼンハムアルゴリズムの導出法（2005/5/14）

ウシオダさんからブレゼンハムアルゴリズムの導出法を教えていただきました。

始点を (a,b) 、終点を (a+Δx, b+Δy) とし、この間に直線を引くことを考えます。ここでは、Δx＞Δy＞0 とします。ある場所、◎ (a+i, b+j) において次に塗りつぶすマスは Δx＞Δy という条件では P(a+i+1, b+j) か Q(a+i+1, b+j+1) のどちらかです。◎の次に塗りつぶすマスとしてPとQのどちらがよいかを判定するのがプログラム中の変数fractionです。

f:id:aidiary:20090829115112g:plain

(a,b) と (a+Δx, b+Δy) をつなぐ理想的な直線の方程式は、

   y = (Δy/Δx)(x - a) + b

となります。つまり、x=a+i+1 における理想的なy座標は上の方程式に x=a+i+1 を代入して

   y = (Δy/Δx)(a+i+1-a) + b
     = (Δy/Δx)(i+1) + b

です。また、PとQの中点のy座標は {(b+j)+(b+j+1)} / 2 より

   b+j+0.5

となります。ここで、x=a+i+1 における理想曲線のy座標とPとQの中点のy座標の差を考えます。

   fraction' = (Δy/Δx)(i+1) + b - (b+j+0.5)

このfraction'を使って、

   fraction' >= 0 ならば Q を選ぶ
   fraction' <  0 ならば P を選ぶ

と判定できます。なぜならfraction'が正ってことは理想曲線のy座標はPよりはQにより近い、fraction'が負ってことは理想曲線のy座標はQよりはPに近いことになるからです。なるべく理想曲線に近くなるようにPかQを選ぶのがコツです。

fraction'は式の中に0.5という小数があります。そのため、fraction'を2Δx倍してfractionとします。

   fraction = 2Δx * fraction'
            = 2Δy(i + 1) - Δx(2j + 1)

fraction'は大小判定に使うだけですので符号が変わらなければ何倍してもかまいません。2Δx > 0 で正数なので符号は変わりません。fractionはかなりすっきりした式になりました。

ここで、

   i（x方向）を1増やすとfractionは2Δy増える
   j（y方向）を1増やすとfractionは2Δx減る

ことに注意してください。また、fractionの初期値は i=0, j=0 なので

   2Δy-Δx

となります。ここでさらにトリックを使って2ΔxをdeltaX、2ΔyをdeltaYに置き換えてみます。すると、

   i（x方向）を1増やすとfractionはdeltaY増える
   j（y方向）を1増やすとfractionはdeltaX減る
   fractionの初期値はdeltaY-deltaX/2

となります。ここでコードを見てみます。

    // ΔxとΔyを2倍してdeltaX、deltaYとする
    deltaX = Math.abs(deltaX * 2);
    deltaY = Math.abs(deltaY * 2);  
        
    if (deltaX > deltaY) {
        fraction = deltaY - deltaX / 2;  // fractionの初期値
        while (nextX != end.x) {
            // fraction>=0のときはQ(a+i+1,b+j+1)を選ぶ
            // つまり、nextX,nextYともに+1
            if (fraction >= 0) {
                nextY += stepY;      // yが1増えると
                fraction -= deltaX;  // fractionはdeltaX減る
            }
            // fraction<0のときはP(a+i+1,b+j)を選ぶ
            // つまり、nextXだけ+1
            nextX += stepX;      // xが1増えると
            fraction += deltaY;  // fractionはdeltaY増える
            line[step] = new Point(nextX, nextY);
            step++;
        }
    }