Bresenham's algorithm with one point and angle

Question

I have a grid whose each cell is determined by its x and y coordinates (integers). This grid is 100x100 wide.

I am given a cell (x0, y0), and an angle A.

My goal is to be able to get the coordinates of all the cells crossed by the line ((x0, y0), A), within the grid.

How can I do that ?? The problem is that I don't have the length of the line...

I was thinking of finding a second point and then use Bresenham's algorithm, but it's too long to compute it because the second point I find is usually outside my grid. Thus I was thinking of modifying Bresenham's algorithm (http://www.roguebasin.com/index.php?title=Bresenham%27s_Line_Algorithm#Python), but I don't have a clue how to do it given that the algorithm is based on the fact that we have two points on the input ! :/

Thank you in advance for your help.

Answer 1

Assume that the angle is such that the line will exit the grid along the x-axis before exiting along the y-axis. This means you know the x co-ordinate of the end of that line, and can compute its y co-ordinate using the formula given by @AxelKemper. (If need be, swap the roles of x & y in the above.) If you can't tell which is the case beforehand, just pick one, do the computation, and if it falls outside the grid, use the other case.

Answer 2

Given that theta = atan2(dy,dx). Here is a Bresenham lineworks with a given slope in the form of dx, dy and a single point (x0,y0). You also need to specify the image space you will be using. That is the minimum and maximum x and y values:

     void line(int x0, int y0, int dx, int dy, int minx, int miny, int maxx, int maxy)
     {
         int  sx = dx > 0 ? 1 : -1;
         int  sy = dy > 0 ? 1 : -1;

         dx = abs(dx);
         dy = abs(dy);

         int err = (dx > dy ? dx : -dy) / 2, e2;

         while (x0 >= minx&& y0 >= miny&& x0 <= maxx && y0 <= maxy)
         {
             std::cout << x0 << "," << y0 << endl; // setPixel(x0, y0);
             e2 = err;
             if (e2 > -dx) { err -= dy; x0 += sx; }
             if (e2 < dy) { err += dx; y0 += sy; }
         }
     }

Example driver:

  void driver()
  {
       vector < pair<int, int>> dxdy = { { -1,0},
        { -1,-1},{0,1},{1,1},{-3,1} };

       for (auto& j : dxdy) {
          std::cout << "dxdy = " << j.first << "," << j.second << endl;
          line(5, 5, j.first, j.second, 0, 0, 10, 10);

      }
  }

Output:
dxdy = -1,0
5,5
4,5
3,5
2,5
1,5
0,5
dxdy = -1,-1
5,5
4,4
3,3
2,2
1,1
0,0
dxdy = 0,1
5,5
5,6
5,7
5,8
5,9
5,10
dxdy = 1,1
5,5
6,6
7,7
8,8
9,9
10,10
dxdy = -3,1
5,5
4,5
3,6
2,6
1,6
0,7