HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Bresenham's line algorithm implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
bresenhamimplementationlinealgorithm

Problem

May there be any performance and/or code standard improvements on the following LineOfSight code?

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

    List returningVector = new List();
    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  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;
}

Solution

The least you could do is move if(steep) out of the for loop, saving one conditional in every iteration.

In the initializations, you could use a swap function.

Why is the name of the function getIntersects?

I don't know C#, but if new Coordinate(x,y) is using the heap for every single point, this does not sound very efficient.

Context

StackExchange Code Review Q#48747, answer score: 4

Revisions (0)

No revisions yet.