如何修改Bresenham';s线性算法来保持秩序

本文关键字:算法 线性 何修改 修改 Bresenham | 更新日期: 2023-09-27 18:26:41

我一直在努力用鼠标在网格上画一条线。我用的是Bresenhams线性算法。

然而,我需要它来保持顺序,所以如果用户向左绘制,它会按该顺序给我分数。

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

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;
}

这是一个我尝试让它工作的版本(它偶尔会陷入一段时间的循环,很难确定原因)

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;
}

感谢

Jim

如何修改Bresenham';s线性算法来保持秩序

在朋友的大力帮助下,这里是最终的解决方案。

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;
}