メメメモモ

プログラミング、筋トレ、ゲーム、etc

Bresenham

perlでBresenhamアルゴリズムを書いてみました。
考え方は下記のような感じ。

  • xが増えたら、\frac{y_2 - y_1}{x_2 - x_1}だけyが増える
  • 整数単位の話なので、\frac{y_2 - y_1}{x_2 - x_1}が1以上になったら、yが1増える
  • \frac{y_2 - y_1}{x_2 - x_1} >= 1じゃなくて、y_2 - y_1 >= x_2 - x_1で比較すれば、割り算が無くなって便利
use strict;
use warnings;


bresenham_line(5,0,20,10);


sub bresenham_line {
    my ($x1, $y1, $x2, $y2) = @_;

    # 距離                                                                      
    my $dx = $x2 - $x1;
    my $dy = $y2 - $y1;

    # 誤差                                                                      
    my $e = 0;

    if ($dx > $dy) {
        for (my $y = $y1, my $x = $x1; $x < $x2; $x++) {
            $e += $dy;
            if ($e > $dx) {
                $e -= $dx;
                $y++;
            }
            print "$x, $y, $dx, $dy, $e\n";
        }
    } else {
        for (my $x = $x1, my $y = $y1; $y < $y2; $y++) {
            $e += $dx;
            if ($e > $dy) {
                $e -= $dy;
                $x++;
            }
            print "$x, $y, $dx, $dy, $e\n";
        }
    }
}