2

ブレゼンハムによる線を描くためのこのよく知られたアルゴリズムがあり、ウィキペディアにはそれに関する非常に良い記事があります: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm。

メイン ループは、必要に応じて 1 を加算または減算して、x または y 座標を繰り返し計算します。

start-point x1、y1、 end-point x2、y2および some y( y1<= y<= ) を指定すると、行のアクティブなピクセルのすべての座標y2を直接計算できますか?xy

たとえば、標準の Bresenham メソッドを使用して線を引くとします。

    oooo               - y1
        ooo
           oooo
               ooo     - y
                  oooo - y2

    |                |
    x1               x2

そのためyに、 のシーケンスを取得したいと思い[x1+11, x1+12, x1+13]ます。

上記のように Bresenham を変更することさえ可能かどうかはわかりませんが、それが不可能であることが判明した場合、Bresenham によって計算された場合とまったく同じに見えるシーケンスを取得する他の方法はありますか? 直接評価できる限り、float を使用するかどうか、速いか遅いかは気にしません。

前もって感謝します！

編集：アイデアを比較できるようにするために、簡単な参照テストを作成しました：

def line(x0, y0, x1, y1):
    canvas = [[u'\u25a1'] * (max(x0, x1) + 1) for y in range(max(y0, y1) + 1)]
    dx = abs(x1-x0)
    dy = abs(y1-y0)
    if x0 < x1:
        sx = 1
    else:
        sx = -1
    if y0 < y1:
        sy = 1
    else:
        sy = -1
    err = dx-dy
    while True:
        canvas[y0][x0] = u'\u25a0'
        if x0 == x1 and y0 == y1:
            break
        e2 = 2*err
        if e2 > -dy:
            err = err - dy
            x0 = x0 + sx
        if e2 < dx:
            err = err + dx
            y0 = y0 + sy
    return '\n'.join(' '.join(r) for r in canvas)

タイピング：

print line(2, 1, 10, 8)

プリント:

□ □ □ □ □ □ □ □ □ □ □
□ □ ■ □ □ □ □ □ □ □ □
□ □ □ ■ □ □ □ □ □ □ □
□ □ □ □ ■ □ □ □ □ □ □
□ □ □ □ □ ■ ■ □ □ □ □
□ □ □ □ □ □ □ ■ □ □ □
□ □ □ □ □ □ □ □ ■ □ □
□ □ □ □ □ □ □ □ □ ■ □
□ □ □ □ □ □ □ □ □ □ ■
4

1 に答える 1

1

ブレゼンハムのアルゴリズムは、整数演算を使用するため魅力的です (ピクセルが整数の x、y 座標にあるという単純化した仮定を作成します)。

ある行のピクセル数を整数 y で解くアルゴリズムは、次のようになります。

count = 1
y_query = your query row
x_intercept = intercept of your line at y_query.
round x_intercept to the nearest integer. 
(x_intercept, y_query) now define a pixel in the row

アイデアは、この座標から左右に移動して、まだ y_query 行にいるかどうかを確認することです。

//going left
x_new = x_intercept - 1
y_new = the y intercept for the line given x_new
round y_new to the nearest integer
if (y_new == y_query), add 1 to our count of pixels in this row, else break;

x_new = x_intercept + 1 についても同じことを行います

于 2013-01-28T02:11:08.623 に答える