0

直線上にあるすべての点を見つける必要があります。Bresenham のアルゴリズムを試しましたが、次のケースでは機能しません。

 (0, 0)
.-----------+-----------+-----------.
|...........|           |           |
|...........|           |           |
|.....XXXX..|           |           |
|........XXXX           |           |
|...........XXXXX       |           |
+-----------+---XXXX----+-----------+
|           |......XXXXX|...........|
|           |..........XXXX.........|
|           |...........|.XXXXX.....|
|           |...........|...........|
|           |...........|...........|
`-----------+-----------+-----------´
                              (2, 1)

Xは実際の線です。.は Bresenham のアルゴリズムが返すものです。線は交差(1, 0)していますが、マークされていないことに注意してください。
ラインが通過するすべてのピクセルを効率的に見つけるにはどうすればよいですか? このアンチエイリアスは必要ないので、Wu のアルゴリズムはやり過ぎだと思います。線の終点はピクセルの中央にあります。

私が持っているアルゴリズムを参照するには:

int dx = System.Math.Abs(x0 - x1);
int dy = System.Math.Abs(y0 - y1);

int sx = x0 < x1 ? 1 : -1;
int sy = y0 < y1 ? 1 : -1;

int err = dx - dy;

int lx = x0;
int ly = y0;

for(int i = 0; true; i++)
{
    Mark(x0, y0);

    if(x0 == x1 && y0 == y1)
        break;

    int e2 = err * 2;
    if(e2 > -dy)
    {
        err -= dy;
        x0 += sx;
    }
    if(e2 < dx)
    {
        err += dx;
        y0 += sy;
    }
}
4

1 に答える 1

1

単純明快なアルゴリズムを実装するだけです: ラインの一方の端から開始し、最初の正方形のどちら側と交差するかを見つけ、対応する隣接する正方形にジャンプします... などです。フィニッシュスクエアに到達するまで歩きます。

整数で実装する最も簡単な方法は、スーパーピクセル精度に切り替えることです。すべてに定数を掛けるだけです。難しい部分は、十分に乗算するのに十分な整数範囲がないことに気付いたときに始まります...これがあなたの場合に当てはまるかどうかはわかりません。

于 2011-05-04T15:26:51.613 に答える