簡素化されたBresenhamのラインアルゴリズム：*正確に*何か？私はそこに記載さ<a href="http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Simplification">simplified version</a>を実装しましたブレゼンハムのアルゴリズム上のWikipediaの記事に基づいて

Question

、私のJava実装は次のようになります。

int dx = Math.abs(x2 - x1); 
int dy = Math.abs(y2 - y1); 

int sx = (x1 < x2) ? 1 : -1; 
int sy = (y1 < y2) ? 1 : -1; 

int err = dx - dy; 

while (true) { 
    framebuffer.setPixel(x1, y1, Vec3.one); 

    if (x1 == x2 && y1 == y2) { 
     break; 
    } 

    int e2 = 2 * err; 

    if (e2 > -dy) { 
     err = err - dy; 
     x1 = x1 + sx; 
    } 

    if (e2 < dx) { 
     err = err + dx; 
     y1 = y1 + sy; 
    } 
} 

今私は、x軸上のステップ間errコントロールの比率を比較することを理解してくださいy軸上のステップに移動しますが、コードが何をしているのかを文書化するようになったので、明確に表現していない、それが何であるのか、なぜか if文は、 errはコードのように変更されています。

ウィキペディアはこれ以上detailled説明や情報源を指していないので、私は思ったんだけど：

何を正確にerrはやるん、なぜdx、正しい比率を維持するために正確に示すように使用dyありますBresenhamのラインアルゴリズムの簡略化されたバージョンを使用して、水平と垂直のステップの間に？

Answer 1

最もよく知られているのは、y=m*x+bの1つのラインの式がいろいろあります。今度はm=dy/dxとc = dx*bの場合、dx*y = dy*x + cです。 f(x) = dy*x - dx*y + cと書くと、f(x,y) = 0 iff (x,y)が与えられた行の点です。

xを1ユニット進めるとf(x,y)はdyに変更されます。 yを1ユニット進めるとf(x,y)がdxに変更されます。コードにおいて 、errはf(x,y)機能線形の電流値を表し、ステートメント配列

err = err - dy; 
    x1 = x1 + sx; 

と

err = err + dx; 
    y1 = y1 + sy; 

は、（sx又はsy方向）x又はy一つのユニットを前進表します結果として関数値に影響を与えます。前述したように、f(x,y)はライン上の点ではゼロです。線の片側の点は正であり、反対側の点は負である。 ifテストでは、の前進が、yの前進よりも望ましい行に近くなるかどうか、またはその逆、またはその両方が決定されます。

初期化err = dx - dy;は、オフセットエラーを最小限に抑えるように設計されています。プロットスケールを吹き飛ばすと、計算されたラインが、異なる初期設定で目的のラインの中央に配置されないことがあります。

Answer 2

「なぜ」の情報をjwpatの優れた答えに追加したいだけです。

f(x) = dy*x - dx*y + cの配合の使用のポイントは、計算を高速化することです。この定式化では整数演算（高速化）が使用されますが、従来のy = mx + bフォーミュレーションでは浮動小数点演算（より遅い）が使用されます。