5
$\begingroup$

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.

Angled line

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 radians = (M_PI/180)*angle;

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Nathan Reed
    Commented Dec 8, 2015 at 19:02
  • $\begingroup$ Hope the addition make it more clear.. $\endgroup$
    – Bob Burt
    Commented Dec 9, 2015 at 16:44
  • $\begingroup$ 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)? $\endgroup$
    – Nathan Reed
    Commented Dec 9, 2015 at 18:07
  • $\begingroup$ yes exactly.. but also that the method only works for slopes within 0-1 $\endgroup$
    – Bob Burt
    Commented Dec 9, 2015 at 18:11

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice.. it works.. :) $\endgroup$
    – Bob Burt
    Commented Dec 9, 2015 at 19:37
  • $\begingroup$ 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.. $\endgroup$
    – Bob Burt
    Commented Dec 9, 2015 at 22:12
  • $\begingroup$ endPos: (15,-2) Angle: 293 $\endgroup$
    – Bob Burt
    Commented Dec 9, 2015 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.