5

Bresenham 線描画アルゴリズムで線を描画する場合、書き込み先のビットマップの境界内に線が入らない場合があります。結果をクリップして、書き込み先の画像の軸に合わせた境界内に収まるようにすると便利です。

最初に線を長方形にクリップしてから線を引くことは可能ですが。これは理想的ではありません。これは、線にわずかに異なる傾斜を与えることが多いためです(int 座標が使用されていると仮定します)。

原始的な操作なので、形を保ったまま線を切り取る方法は確立されているのでしょうか？

それが役立つ場合は、アルゴリズムの参照実装を次に示します。これは、線の描画中に int/float 変換を回避する int 座標を使用します。

私はこれを調べるのにしばらく時間を費やしました：

4

2 に答える 2

2

Bresenham のアルゴリズムが実際にどのように機能するかを確認できるように、問題を再構成してみましょう...

ほぼ水平の線を描いているとしましょう (方法はほぼ垂直の場合と同じですが、軸が切り替えられます)(x0,y0)から(x1,y1):

y完全な行は、x(すべての整数)の関数として記述できます。

y = y0 + round( (x-x0) * (y1-y0) / (x1-x0) )

これは、完全な線を描画するときにペイントする各ピクセルを正確に記述し、線を一貫してクリップする場合でも、ペイントする各ピクセルを正確に記述します-値のより小さな範囲に適用するだけxです.

除数と剰余を別々に計算することにより、すべての整数演算を使用してこの関数を評価できます。x1 >= x0andの場合y1 >= y0(それ以外の場合は通常の変換を行います):

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
    rem-=dx;
    y+=1;
}

Bresenham のアルゴリズムは、この式の結果を の更新に応じてインクリメンタルに更新する簡単な方法ですx。

増分更新を使用して、まったく同じ線の x=xs から x=xe までの部分を描画する方法を次に示します。

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

x=xs;
rem = (x-x0) * dy % dx;
y = y0 + (x-x0) * dy / dx;
if (rem >= remlimit)
{
    rem-=dx;
    y+=1;
}
paint(x,y);
while(x < xe)
{
    x+=1;
    rem+=dy;
    if (rem >= remlimit)
    {
        rem-=dx;
        y+=1;
    }
    paint(x,y);
}

0 に対する余りの比較を行いたい場合は、最初にそれをオフセットすることができます。

let dx = (x1-x0);
let dy = (y1-y0);
let remlimit = (dx+1)/2; //round up

x=xs;
rem = ( (x-x0) * dy % dx ) - remlimit;
y = y0 + (x-x0) * dy / dx;
if (rem >= 0)
{
    rem-=dx;
    y+=1;
}
paint(x,y);
while(x < xe)
{
    x+=1;
    rem+=dy;
    if (rem >= 0)
    {
        rem-=dx;
        y+=1;
    }
    paint(x,y);
}
于 2016-11-30T14:13:25.000 に答える