type point = (int * int);;

let point_a : point = (0, 0)
and point_b : point = (4, 3);;

type segment = point array;;

let bresenham (a : point) (b : point) : segment =
  let a1, a2 = a
  and b1, b2 = b in
  let n = b1 - a1 in
  let segment_ab = Array.make (n+1) a in
  let alpha_normalisee = b2 - a2 in (* pente normalisée, ie alpha*n dans *)
  let erreur = ref 0 in
  let y_tilde = ref a2 in
  for i = 1 to n-1 do
    if 2 * (!erreur + alpha_normalisee) <= n then
      erreur := !erreur + alpha_normalisee
    else begin
      erreur := !erreur + alpha_normalisee - n;
      y_tilde := !y_tilde + 1;
    end;
    segment_ab.(i) <- (a1 + i, !y_tilde);
  done;
  segment_ab.(n) <- b;
  segment_ab
;;

bresenham (0, 0) (5, 2);;

bresenham (0, 0) (5, 5);;

bresenham (0, 0) (-5, 2);;

bresenham (0, 0) (0, 2);;

let au_plus_pres_inferieurement (a : point) (b : point) : segment =
  let a1, a2 = a
  and b1, b2 = b in
  let n = b1 - a1 in
  let segment_ab = Array.make (n+1) a in
  let alpha_normalisee = b2 - a2 in (* pente normalisée, ie alpha*n dans *)
  for i = 1 to n-1 do
    (* on laisse la division entière faire la partie inférieure *)
    segment_ab.(i) <- (a1 + i, (alpha_normalisee * i + a2 * (b1-a1)) / (b1 -a1));
  done;
  segment_ab.(n) <- b;
  segment_ab
;;

bresenham (0, 0) (5, 2);;
au_plus_pres_inferieurement (0, 0) (5, 2);;

bresenham (0, 0) (5, 5);;
au_plus_pres_inferieurement (0, 0) (5, 5);;

ceil;;

let ceil_to_int x = int_of_float (ceil x);;

let au_plus_pres_superieurement (a : point) (b : point) : segment =
  let a1, a2 = a
  and b1, b2 = b in
  let n = b1 - a1 in
  let segment_ab = Array.make (n+1) a in
  let alpha = (float_of_int (b2 - a2)) /. (float_of_int n) in (* pente normalisée, ie alpha*n dans *)
  for i = 1 to n-1 do
    segment_ab.(i) <- (a1 + i, ceil_to_int ((float_of_int a2) +. alpha *. (float_of_int i)));
  done;
  segment_ab.(n) <- b;
  segment_ab
;;

bresenham (0, 0) (5, 2);;
au_plus_pres_superieurement (0, 0) (5, 2);;

bresenham (0, 0) (5, 5);;
au_plus_pres_superieurement (0, 0) (5, 5);;

type mot_binaire = bool array;;

let deplacements (a : point) (b : point) : mot_binaire =
  let a1, a2 = a
  and b1, b2 = b in
  let n = b1 - a1 in
  let mot_binaire_ab : mot_binaire = Array.make n false in
  let alpha_normalisee = b2 - a2 in (* pente normalisée, ie alpha*n dans *)
  let y0 = ref 0 and y1 = ref 0 in
  for i = 1 to n do
    y0 := !y1;
    (* on laisse la division entière faire la partie inférieure *)
    y1 := (alpha_normalisee * i + a2 * (b1-a1)) / (b1 -a1);
    mot_binaire_ab.(i-1) <- !y0 != !y1;
  done;
  mot_binaire_ab
;;

au_plus_pres_inferieurement (0, 0) (5, 2);;
deplacements (0, 0) (5, 2);;

au_plus_pres_inferieurement (0, 0) (5, 5);;
deplacements (0, 0) (5, 5);;