Bresenham线算法的实现

Question

下面的LineOfSight代码是否有任何性能和/或代码标准改进？

static List<Coordinate> getIntersects(Coordinate c1, Coordinate c2) {
    //  Bresenham's line algorithm from http://rosettacode.org/wiki/Bitmap/Bresenham's_line_algorithm#C.2B.2B

    List<Coordinate> returningVector = new List<Coordinate>();
    double y1 = c1.y, x1 = c1.x, y2 = c2.y, x2 = c2.x;

    bool steep = (Math.Abs(y2 - y1) > Math.Abs(x2 - x1)); 
    if(steep)
    {
        double _t;
        _t = x1;
        x1 = y1;
        y1 = _t;
        _t = x2;
        x2 = y2;
        y2 = _t;
    }

    if(x1 > x2)
    {
        double _t;
        _t = x1;
        x1 = x2;
        x2 = _t;
        _t = y1;
        y1 = y2;
        y2 = _t;
    }

    double dx = x2 - x1;
    double dy = Math.Abs(y2 - y1);

    double error = dx / 2.0f;
    int ystep = (y1 < y2) ? 1 : -1;
    int y = (int)y1;

    int maxX = (int)x2;

    for(int x=(int)x1; x<maxX; x++)
    {
        if(steep)
        {
            Coordinate tc = new Coordinate(y, x);
            returningVector.Add(tc);
        }
        else
        {
            Coordinate tc = new Coordinate(x,y);
            returningVector.Add(tc);
        }

        error -= dy;
        if(error < 0)
        {
            y += ystep;
            error += dx;
        }
    }
    if(steep)
    {
        Coordinate tc = new Coordinate(y2, x2);
        returningVector.Add(tc);
    }
    else
    {
        Coordinate tc = new Coordinate(x2,y2);
        returningVector.Add(tc);
    }
    return returningVector;
}

static bool isObstacle(Coordinate c1, Coordinate c2, Coordinate c3) {
    double heightOn_c3 = Math.Abs(((c1.height - c2.height) * Tools.distanceXY(c2, c3)) / Tools.distanceXY(c2, c1));
    return (heightOn_c3 + c2.height) < c3.height;
}

public static bool calculateLOS(Coordinate c1, Coordinate c2, Map map) {
    List<Coordinate> intersects = getIntersects(c1, c2);
    for(int i=0; i<intersects.Count; i++) {
        if(isObstacle(c1, c2, map.points[(int)intersects[i].x][(int)intersects[i].y].coordinates)){
            return false;
        }
    }
    return true;
}

Answer 1

至少您可以将if(steep)从for循环中移出，在每次迭代中保存一个条件。

在初始化过程中，可以使用swap函数。

为什么函数的名称是getIntersects？

我不知道C#，但是如果new Coordinate(x,y)对每个点都使用堆，这听起来不太有效。

Answer 2

公约：

在我看来，这绝对是当前代码中最大的问题。命名惯例。所有程序员都同意，命名是最困难的事情之一。因此，在命名时定义要遵守的约定是有用的。命名方法的C#约定不是camelCase，而是PascalCase。

接下来是getIntersects方法中的局部变量。

首先要批评的是你的参数名称。你应该远离变量名中的数字。而是前缀first、second等等。或者添加一个后缀，比如One，Two.

这里的另一件事是放置花括号，C#惯例是，每个花括号都应该有自己的行(使用，埃及大括号)。

重写一下您的getIntersects：

static GetIntersects(Coordinate firstCooridinate, Coordinate secondCoordinate)
{
    List<Coordinate> returningVector = new List<Coordinate>();
    double firstY = firstCoordinate.y;
    double firstX = firstCoordinate.x;
    double secondY = secondCoordinate.y;
    double secondX = secondCoordinate.x;

    bool isSteep = (Math.Abs(secondY - firstY) > Math.Abs(secondX - firstX));
    if(isSteep)
    {
        Swap(ref firstX, ref firstY);
        Swap(ref secondX, ref secondY);
    }

    if(firstX > secondX)
    {
        Swap(ref firstX, ref secondX);
        Swap(ref firstY, ref secondY);
    }

    double deltaX = secondX - firstX;
    double deltaY = Math.Abs(secondY - firstY);

    double error = deltaX / 2.0f;
    int ySteps = (firstY < secondY) ? 1 : -1;
    int maxX = int secondX;

    //stopping here, the rest is yours to write.
}

访问修饰符：

您应该始终显式地写出访问修饰符。这说明了你的方法应该被用来.

小尼采：

就我个人而言，我更喜欢在赋值状态中不超过两个括号。预先计算您在作业中使用的内容，当您很好地命名它们时，您在上面有免费的文档;)

Answer 3

我将进一步研究Vogel612重构，并在您的坐标类中实现一些更多的逻辑，这样我就可以有一个更整洁的GetIntersects方法。我也会去掉所有这些变量，并尽可能多地使用坐标X和Y。

public class Coordinate{
    public int X{get; set;}
    public int Y{get; set;}

    public Coordinate(){}

    public Coordinate(int x, int y){
        X = x;
        y = y;
    }

    public static Coordinate operator +(Coordinate c1, Coordinate c2){
        return new Coordinate(){
            X = c1.X + c2.X,
            Y = c1.Y + c2.Y
        };
    }

    public static Coordinate operator -(Coordinate c1, Coordinate c2){
        return new Coordinate(){
            X = c1.X - c2.X,
            Y = c1.Y - c2.Y
        };
    }

    public void Swap(){
        int aux = X;
        X = Y;
        Y = aux;
    }

    public override string ToString(){
        return string.Format("Coordinate ({0}, {1})", X, Y);
    }
}

static List<Coordinate> getIntersects(Coordinate c1, Coordinate c2) {
    List<Coordinate> returningVector = new List<Coordinate>();

    bool steep = (Math.Abs(c2.Y - c1.Y) > Math.Abs(c2.X - c1.X)); 
    if(steep)
    {
        c1.Swap();
    }

    if(c1.X > c2.X)
    {
        Coordinate aux = c1;
        c1 = c2;
        c2 = aux;
    }

    Coordinate dc = c2 - c1;
    dc.Y = Math.Abs(dc.Y);

    double error = dc.X / 2.0f;
    int ystep = (c1.Y < c2.Y) ? 1 : -1;
    int y = dc.Y;
    for(int x = c1.X; x < c2.X; x++)
    {
        if(steep)
        {
            Coordinate tc = new Coordinate(y, x);
            returningVector.Add(tc);
        }
        else
        {
            Coordinate tc = new Coordinate(x, y);
            returningVector.Add(tc);
        }

        error -= y;
        if(error < 0)
        {
            y += ystep;
            error += dc.X;
        }
    }
    if(steep)
    {
        Coordinate tc = new Coordinate(c2.Y, c2.X);
        returningVector.Add(tc);
    }
    else
    {
        Coordinate tc = new Coordinate(c2.X,c2.Y);
        returningVector.Add(tc);
    }
    return returningVector;
}

如果我把X放错了Y <.<，请不要怪我