如何修改 Bresenham 的线算法以保持顺序？

Question

我一直在尝试用粘附在网格上的鼠标画一条线。我正在使用 Bresenhams 线算法。

但是我需要它来保留顺序，所以如果用户向左绘图，它会按照该顺序给我分数。

WorldTile 是一个 class，充当网格上的一个节点。

WorldBoard 是一组 WorldTiles。

private static void Swap<T>(ref T lhs, ref T rhs) 
{
    T temp; 
    temp = lhs; 
    lhs = rhs; 
    rhs = temp; 
}

public static IEnumerable<WorldTile> GetWorldTilesOnLine(int x0, int y0, int x1, int y1)
{


    bool steep = Mathf.Abs(y1 - y0) > Mathf.Abs(x1 - x0);

    if (steep)
    { 
        Swap<int>(ref x0, ref y0); // find out how this works
        Swap<int>(ref x1, ref y1); 
    }

    if (x0 > x1)
    {
        Swap<int>(ref x0, ref x1); 
        Swap<int>(ref y0, ref y1);
    }


    int dx = (x1 - x0);
    int dy = Mathf.Abs(y1 - y0);
    int error = (dx / 2); 
    int ystep = (y0 < y1 ? 1 : -1);
    int y = y0;

    for (int x = x0; x <= x1; x++)
    {
        yield return worldBoard[(steep ? y : x), (steep ? x : y)];
        error = error - dy;
        if (error < 0)
        {
            y += ystep;
            error += dx;
        }
    }
    yield break;
}

这是我尝试让它工作的一个版本（它偶尔会卡在 while 循环中，很难找出原因）

public static IEnumerable<WorldTile> GetWorldTilesOnLine(int x0, int y0, int x1, int y1)
{
    int dy = (int)(y1-y0);
    int dx = (int)(x1-x0);
    int xstep = 1;
    int ystep = 1;

    if (dy < 0) {dy = -dy; xstep = -1;}
    else {ystep = 1;}
    if (dx < 0) {dx = -dx; ystep = -1;}
    else {xstep = 1;}
    dy <<= 1;
    dx <<= 1;

    float fraction = 0;
    //Debug.Log (xstep);

    if (x0 >= 0 && x0 < worldBoard.GetLength(0) && y0 >= 0 && y0 <  worldBoard.GetLength(1))
    {
        yield return worldBoard[x0, y0];
    }

    if (dx > dy) {
        fraction = dy - (dx >> 1);

        while (Mathf.Abs(x0 - x1) > 1) {

            if (fraction >= 0) {
                y0 += ystep;
                fraction -= dx;
            }
            x0 += xstep;
            fraction += dy;
            if (x0 >= 0 && x0 < worldBoard.GetLength(0) && y0 >= 0 && y0 < worldBoard.GetLength(1))
            {
                yield return worldBoard[x0, y0];
            }
        }
    }
    else {
        fraction = dx - (dy >> 1);

        while (Mathf.Abs(y0 - y1) > 1) {
            if (fraction >= 0) {
                x0 += xstep;
                fraction -= dy;
            }
            y0 += ystep;
            fraction += dx;
            if (x0 >= 0 && x0 < worldBoard.GetLength(0) && y0 >= 0 && y0 < worldBoard.GetLength(1))
            {
                yield return worldBoard[x0, y0];
            }
        }
    }
    yield break;
}

谢谢

吉姆

Answer 1

在朋友的大力帮助下终于解决了。

WorldBoard 是一组 WorldTiles。

WorldTiles 本质上是网格上的节点。

private static void Swap<T>(ref T lhs, ref T rhs) 
{
    T temp; 
    temp = lhs; 
    lhs = rhs; 
    rhs = temp; 
}

public static IEnumerable<WorldTile> GetWorldTilesOnLine(int x0, int y0, int x1, int y1)
{
    bool steep = Mathf.Abs(y1 - y0) > Mathf.Abs(x1 - x0);

    if (steep)
    {
        Swap<int>(ref x0, ref y0);
        Swap<int>(ref x1, ref y1);
    }

    int dx = Mathf.Abs(x1 - x0);
    int dy = Mathf.Abs(y1 - y0);
    int error = (dx / 2);
    int ystep = (y0 < y1 ? 1 : -1);
    int xstep = (x0 < x1 ? 1 : -1);
    int y = y0;

    for (int x = x0; x != (x1 + xstep); x += xstep)
    {
        yield return worldBoard[(steep ? y : x), (steep ? x : y)];
        error = error - dy;
        if (error < 0)
        {
            y += ystep;
            error += dx;
        }
    }
    yield break;
}

如何修改 Bresenham 的线算法以保持顺序？

How can I modify Bresenham's line algorithm to preserve order?

c#

algorithm

unity3d

rasterizing