12

4 連結線を描画するためのアルゴリズム (Java でコード化されていれば問題ありませんが、Java に変換するのに十分明確なものであれば問題ありません) を探しています。Bresenham のアルゴリズムが最も広く使用されているようですが、私が見つけた理解可能な実装はすべて 8 連結です。OpenCV のcvline関数には明らかに 4 接続バージョンがありますが、ソース コードは、凡庸でほとんど C を理解できないプログラマーである私にとって、理解できないものです。他のさまざまな検索では何も見つかりませんでした。

誰でも提供できるヘルプをありがとう。

4

2 に答える 2

16

以下は、ブレゼンハムに似た 4 連結線を描画するアルゴリズムです。コードは Python ですが、言語を知らなくても簡単に理解できると思います。

def line(x0, y0, x1, y1, color):
    dx = abs(x1 - x0)    # distance to travel in X
    dy = abs(y1 - y0)    # distance to travel in Y

    if x0 < x1:
        ix = 1           # x will increase at each step
    else:
        ix = -1          # x will decrease at each step

    if y0 < y1:
        iy = 1           # y will increase at each step
    else:
        iy = -1          # y will decrease at each step

    e = 0                # Current error 

    for i in range(dx + dy):
        draw_pixel(x0, y0, color)
        e1 = e + dy
        e2 = e - dx
        if abs(e1) < abs(e2):
            # Error will be smaller moving on X
            x0 += ix
            e = e1
        else:
            # Error will be smaller moving on Y
            y0 += iy
            e = e2

アイデアは、線を描くには、理論上の線の DX/DY に一致する比率で X と Y をインクリメントする必要があるということです。これを行うには、0 に初期化されたエラー変数から開始しe(ライン上にあります)、各ステップで、X のみをインクリメントするか、Y のみをインクリメントするかによってエラーが小さくなるかどうかをチェックします (ブレゼンハム チェックは、 X のみ、または X と Y の両方)。

このチェックを行うための単純なバージョンは1/dyorを追加すること1/dxですが、すべてのインクリメントを で乗算するdx*dyと、整数値のみを使用できるようになり、速度と精度の両方が向上し、特別なケースの必要性が回避されdx==0、dy==0ロジックが簡素化されます。もちろん、比率エラーを探しているので、スケーリングされた増分を使用しても結果には影響しません。

ライン象限が何であれ、インクリメントの2つの可能性は常にエラーに異なる符号の影響を与えます...したがって、私の任意の選択は、Xステップのエラーをインクリメントし、Yステップのエラーをデクリメントすることでした.

および変数はix、iy初期座標が最終座標よりも低いか高いかに応じて、ラインに必要な実際の方向 (+1 または -1) です。

4 連結線で描画するピクセル数は明らかにdx+dyであるため、終点に到達したかどうかを確認するのではなく、その回数だけループして線を描画します。このアルゴリズムは、最後のピクセルを除くすべてのピクセルを描画することに注意してください。その最終ピクセルも必要な場合draw_pixelは、ループの終了後に追加の呼び出しを追加する必要があります。

上記の実装の結果の例を次の図に示します。

ここに画像の説明を入力

于 2011-03-03T22:50:10.380 に答える
6

Python の読み書きができない人のために、6502 のコードの C バージョンを次に示します。

void drawLine(int x0, int y0, int x1, int y1) {
    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int sgnX = x0 < x1 ? 1 : -1;
    int sgnY = y0 < y1 ? 1 : -1;
    int e = 0;
    for (int i=0; i < dx+dy; i++) {
        drawPixel(x0, y0);
        int e1 = e + dy;
        int e2 = e - dx;
        if (abs(e1) < abs(e2)) {
            x0 += sgnX;
            e = e1;
        } else {
            y0 += sgnY;
            e = e2;
        }
    }
}
于 2013-01-24T16:43:28.953 に答える