12

ウィキペディアの Bresenham のライン アルゴリズムに関する記事に基づいて、そこで説明されている簡略化されたバージョンを実装しました。私の 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;
    }
}

errこれで、y 軸のステップと比較した x 軸のステップの比率を制御することが理解できました。 if ステートメントが正確になぜ、どのようerrに、コードに見られるように変更されたのか。

ウィキペディアはこれ以上詳細な説明や情報源を示していないので、私は疑問に思っています:

Bresenham のライン アルゴリズムの単純化されたバージョンを使用して、水平ステップと垂直ステップの間の正しい比率を維持するために、正確に何errをし、なぜ正確に示されている方法dxで使用されているのでしょうか?dy

4

2 に答える 2

13

線にはさまざまな形式の方程式があり、最もよく知られているのはy=m*x+bです。今ならm=dy/dx、c = dx*bそしてdx*y = dy*x + c。と書くf(x) = dy*x - dx*y + cと、f(x,y) = 0iff(x,y)は与えられた行上の点です。

x1ユニット進むと、 でf(x,y)変わりdyます。y1単位進むと、 だけf(x,y)変化しdxます。コードでerrは、線形汎関数の現在の値を表し、f(x,y)ステートメント シーケンス

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

と

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

関数値に結果として影響を与える前進xまたはy1 単位 (方向sxまたは方向) を表します。sy前に述べたように、f(x,y)は線上の点ではゼロです。線の片側の点は正、反対側の点は負です。ifテストは、advanced がadvanced よりも目的の行に近づくか、その逆か、またはその両方かを判断しxますy。

初期化err = dx - dy;は、オフセット エラーを最小限に抑えるように設計されています。プロットスケールを大きくすると、計算された線が異なる初期化で目的の線の中心にない場合があることがわかります。

于 2011-11-13T19:03:08.027 に答える
1

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

定式化のポイントはf(x) = dy*x - dx*y + c、計算を高速化することです。この定式化では整数演算が使用されますが (高速)、従来のy = mx + b定式化では浮動小数点演算が使用されます (低速)。

于 2013-11-03T01:10:34.390 に答える