srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

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

与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズムである。y = ax + b を近似する場合、ある整数 x に対して、y の値を計算し、その値を四捨五入して整数値にした値を近似値とすればよい。

この操作を始点から終点までのすべての x に対して行えば良いのだが、それだと無駄な計算が多いので効率化したのがこのアルゴリズムである。

ブレゼンハムのアルゴリズム - Wikipedia

以下にこのアルゴリズムC言語で実装したプログラムである。line の方は浮動小数点演算を使用して、アルゴリズムをそのまま実装したもので、line_fastline の中で使われている浮動小数点演算をなくし、整数演算のみで行ったものである。どのようにして浮動小数点演算を整数演算に変換するかだが、 浮動小数点演算が使われているところが整数値になるように、2*dx をかけることで e = e + de >= 0.5 が整数演算に置きかわる。

http://sioramen.sub.jp/algorithm-bresenham/bresenham.html

#include <bits/stdc++.h>
using namespace std;

void plot(int x, int y) {
    printf("%d %d\n", x, y);
}

void line(int xa, int xb, int ya, int yb) {
    assert(xa < xb && ya < yb);
    int dx = xb - xa;
    int dy = yb - ya;
    double d = (double)dy / dx;
    assert(0. <= d && d < 1.);

    double e = 0.;
    int y = ya;
    for (int x = xa; x <= xb; ++x) {
        plot(x, y);
        e = e + d;
        if (e >= 0.5) {
            y++;
            e = e - 1;
        }
    }
}


void line_fast(int xa, int xb, int ya, int yb) {
    assert(xa < xb && ya < yb);
    int dx = xb - xa;
    int dy = yb - ya;
    assert(dy < dx);

    int e = 0;
    int y = ya;
    for (int x = xa; x <= xb; ++x) {
        plot(x, y);
        e = e + 2 * dy;
        if (e >= dx) {
            y++;
            e = e - 2 * dx;
        }
    }
}


int main(int argc, char const *argv[])
{
    // Ex) (x, y):  (2, 3) -> (8, 6);
    int xa = 2, xb = 8, ya = 3, yb = 6;
    printf("line\n");
    line(xa, xb, ya, yb);
    printf("\n");
    printf("line_fast\n");
    line_fast(xa, xb, ya, yb);

    return 0;
}