# Draw angles lines in raster graphics using bresenham line algorithm

I at the moment trying to draw some angled lines using bresenham line algorithm which can circulate a 2d array of size 21x21, as a line angled from 0 - 2pi.

So the idea is that the program has to output the values which the lines pass through in the grid..

So an example with 5x5

Angle:0
_ _ _ _ _
|_|_|_|_|_|
|_|_|_|_|_|
|_|_|.|.|.|
|_|_|_|_|_|
|_|_|_|_|_|

Angle: 45
_ _ _ _ _
|_|_|_|_|.|
|_|_|_|.|_|
|_|_|.|_|_|
|_|_|_|_|_|
|_|_|_|_|_|


and so on..

The problem here is that it doesn't look like that my program does that.. The endpoint lies within the given radius length..

I am sure am might that I might be messing up with the math.. So i hope some of you could help me here..

#include <iostream>
#include <math.h>
using namespace std;
typedef std::pair<int,int> coordinate;

int sign(double x ){ return (x > 0) ? 1 : ((x < 0) ? -1 : 0); }

coordinate endpoint(double angle, int x1 , int y1, int lenght)
{

double x2 = x1 + (lenght * cos(radians));
double y2 = y1 + (lenght * sin(radians));

return std::make_pair(round(x2),round(y2));
}

void bresenham(coordinate start, coordinate end)
{
//restriction a.x < b.x  and 0 < H/W < 1
int y =  start.second;
int w = end.first - start.first;
int h = end.second - start.second;
int f = 2*h-w; // current error term

for (int x = start.first; x<= end.first; x++)
{
cout << "mark: " << x << "," << y << endl;
if (f < 0)
{
f = f + 2*h;
}
else
{
y++;
f=f+2*(h-w);
}
}
}

int main(int argc, const char * argv[])
{

coordinate start = make_pair(0,0);
for (int i = 0; i <= 45; i++)
{
coordinate end = endpoint(i,0,0,10);
cout << "    endPos: "<< "(" << end.first <<","  << end.second   <<")"    << " Angle: " << i << "       " << endl;
cout << "--------------------------------------------" << endl;
bresenham(start, end);
cout << "--------------------------------------------" << endl;
}

return 0;
}


Here is the output.

    endPos: (10,0) Angle: 0
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,0
mark: 6,0
mark: 7,0
mark: 8,0
mark: 9,0
mark: 10,0
--------------------------------------------
endPos: (10,0) Angle: 1
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,0
mark: 6,0
mark: 7,0
mark: 8,0
mark: 9,0
mark: 10,0
--------------------------------------------
endPos: (10,0) Angle: 2
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,0
mark: 6,0
mark: 7,0
mark: 8,0
mark: 9,0
mark: 10,0
--------------------------------------------
endPos: (10,1) Angle: 3
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 4
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 5
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 6
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 7
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,1) Angle: 8
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
endPos: (10,2) Angle: 9
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 10
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 11
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 12
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 13
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,2) Angle: 14
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
endPos: (10,3) Angle: 15
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
endPos: (10,3) Angle: 16
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
endPos: (10,3) Angle: 17
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
endPos: (10,3) Angle: 18
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
endPos: (9,3) Angle: 19
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,3
mark: 9,3
--------------------------------------------
endPos: (9,3) Angle: 20
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,3
mark: 9,3
--------------------------------------------
endPos: (9,4) Angle: 21
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 22
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 23
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 24
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 25
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,4) Angle: 26
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
endPos: (9,5) Angle: 27
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (9,5) Angle: 28
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (9,5) Angle: 29
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (9,5) Angle: 30
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (9,5) Angle: 31
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
endPos: (8,5) Angle: 32
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,3
mark: 5,3
mark: 6,4
mark: 7,4
mark: 8,5
--------------------------------------------
endPos: (8,5) Angle: 33
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,3
mark: 5,3
mark: 6,4
mark: 7,4
mark: 8,5
--------------------------------------------
endPos: (8,6) Angle: 34
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 35
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 36
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 37
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 38
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 39
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,6) Angle: 40
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
endPos: (8,7) Angle: 41
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,4
mark: 6,5
mark: 7,6
mark: 8,7
--------------------------------------------
endPos: (7,7) Angle: 42
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------
endPos: (7,7) Angle: 43
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------
endPos: (7,7) Angle: 44
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------
endPos: (7,7) Angle: 45
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------


What am i doing wrong?... I know that the bresenham algorithm might have to be modified to overcome slopes greater 1 and lower that 0.

Clarifying the problem

I am trying the iterate the 2d array in a circular manner, using bresenham line algorithm .

The algorithm should start from the center of the 2d array, and "shoot out" a beam at angles between 0 - 2pi. The beam has to start from the center and end at the edge of the matrix, Hope it makes more sense..

 _ _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|.|.|.|.|.|.|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|

_ _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|.|.|
|_|_|_|_|_|_|_|_|.|_|_|
|_|_|_|_|_|_|_|.|_|_|_|
|_|_|_|_|_|_|.|_|_|_|_|
|_|_|_|_|_|.|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|


I want to output the values the beam hits on the matrix, at each angle.. Which i don't get.. I want to sample the points which the beam intersect in the matrix..

• Scrolling through your output quickly, it looks reasonable. Although it's hard to tell since it's not plotted as an image. Can you clarify what the problem is? Dec 8, 2015 at 19:02
• Hope the addition make it more clear.. Dec 9, 2015 at 16:44
• Hmmm...it's still not very clear to me. Is the problem that e.g. at a 45 degree angle, the line only goes out to (7, 7) and stops, instead of going all the way out to the corner at e.g. (10, 10)? Dec 9, 2015 at 18:07
• yes exactly.. but also that the method only works for slopes within 0-1 Dec 9, 2015 at 18:11

The endpoint of the line doesn't extend out to the edge of the box because you're using the circle equation with a fixed radius:

double x2 = x1 + (lenght * cos(radians));
double y2 = y1 + (lenght * sin(radians));


This makes the endpoint trace out a circle as the angle is changed.

If you want the endpoint to be on the edge of the box, one way is to set up a ray from the center of the box at the desired angle, then calculate the intersection point of the ray with the box. This article shows how to calculate ray/box intersections.

Another way is to loop over the points around the sides of the box, rather than looping over angles. You would have four separate loops, one for each side, and holding one of x or y fixed while iterating the other. For example, holding x = 10 and iterating y from -10 to +10 would go up the right side.

As for the slopes outside [0, 1], you must extend your Bresenham algorithm for it. This can be found in any tutorial or sample of Bresenham, for example the implementations here.

• Nice.. it works.. :) Dec 9, 2015 at 19:37
• well.. partly seem to have an issue with negative values.. Some end position contains negative values.. the center is here 10,10.. thereby making the matrix sized 20X20.. Dec 9, 2015 at 22:12
• endPos: (15,-2) Angle: 293 Dec 9, 2015 at 22:17