# Bresenham's line algorithm implementation

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

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);
}
else
{
Coordinate tc = new Coordinate(x,y);
}

error -= dy;
if(error < 0)
{
y += ystep;
error += dx;
}
}
if(steep)
{
Coordinate tc = new Coordinate(y2, x2);
}
else
{
Coordinate tc = new Coordinate(x2,y2);
}
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;
}

• This looks like Java code that had bits changed here and there to turn it into C#. – cHao May 2 '14 at 22:20

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.

## Conventions:

That is in my eyes the definitely biggest problem in your current code. Naming conventions. All programmers agree, that naming is one of the most difficult things to do. Therefore it is useful to define conventions to abide when naming. The C# convention for naming methods is not camelCase, but PascalCase.

Next up, your local variables in the getIntersects method.

first thing to criticise is your parameternames. You should stay away from numbers in variable names. Rather prefix first, second, and so on. Or alternatively add a postfix like One, Two...

Another thing here is your placement of curly braces, the C# convention is, that every Curly brace should have it's own line (you use the Java-Convention, egyptian braces).

Rewriting your getIntersects a bit:

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


### Access Modifiers:

You should always explicitly write out the access modifiers. This makes clear what your methods are supposed to be used for...

### Minor Nitpicks:

Personally I prefer not to have more than two parentheses in an assignment statment. Precalculate things you use in the assignment and when you name them nicely, you have free documentation on top of it ;)

• you can't swap value types like double, at least not if the parameter is not passed by reference. – Bruno Costa May 2 '14 at 7:43
• I would also put the swap method on coordinate class if I had access to that class. Calling firstCoordinate.Swap() would be more interesting imo – Bruno Costa May 2 '14 at 7:46
• Really, what is wrong with x1, x2? – iavr May 2 '14 at 7:47
• @iavr what is wrong with _t? why do you want to sacrifice easy readability and thus understanding for character count? – Vogel612 May 2 '14 at 7:48
• @BrunoCosta the problem is, he also swaps between the coordinates... Swap(ref firstY, ref secondY) – Vogel612 May 2 '14 at 7:48

I would take Vogel612 refactoring even further and implement some more logic in your Coordinate class so I can have a tidier looking GetIntersects method. I would also get rid all of those variables and use coordinates X and Y as much as possible.

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);
}
else
{
Coordinate tc = new Coordinate(x, y);
}

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