Bresenham Algorithm

bresenham.cpp

// a point
struct pt {
  int x;
  int y;
};

/*
  Bresenham algorithm.

  Finds successive points on the line (x0, y0) - (x1, y1). 
*/
void bresenham (int x0, int y0, int x1, int y1, std::vector<pt>& points)
{
  int dx = abs (x1 - x0);
  int sx = x0 < x1 ? 1 : -1;
  int dy = -abs (y1 - y0);
  int sy = y0 < y1 ? 1 : -1;
  int error = dx + dy;

  while (1)
  {
    points.push_back ({ x0, y0 });
    if (x0 == x1 && y0 == y1)
      break;
    int e2 = 2 * error;
    if (e2 >= dy)
    {
      if (x0 == x1)
        break;
      error = error + dy;
      x0 = x0 + sx;
    }
    if (e2 <= dx)
    {
      if (y0 == y1)
        break;
      error = error + dx;
      y0 = y0 + sy;
    }
  }
}