Created by Lilian Besson (Naereen) last modified Lilian Besson 2017-05-18

bresenham_droites.ml

      (** <h1>Représentation des segments en infographie.</h1>

    <h1>Prépa. agreg 2013-2014 : Texte de Modélisation.</h1>

    <b>Date:</b> Mardi 29 Avril 2014.
    @see <http://besson.qc.to/a/m/29-04/public2012-D5.pdf> Sujet.
    @see <http://besson.qc.to/a/m/29-04/> Documentation.
    @author Lilian BESSON
*)


(** <h2>Préliminaires.</h2> *)

(** <h3>Type [point] pour représenter un point [A = (a1, a2)].</h3> *)

type point = int * int;;

(** Deux points, venant de l'exemple de la <b>Figure 1</b>. *)

let a : point = (0, 0)
and b : point = (18, 7) ;;


(** <h3>Type [segment] pour représenter un segment, sous forme de liste de points.</h3> *)

type segment = point array;;

(** L'exemple de la <b>Figure 1</b>. *)

let d1 : segment = [|
  (0, 0);
  (1, 0);
  (2, 1);
  (3, 1);
  (4, 1);
  (5, 2);
  (6, 2);
  (7, 3);
  (8, 3);
  (9, 3);
  (10, 4);
  (11, 4);
  (12, 4);
  (13, 5);
  (14, 5);
  (15, 5);
  (16, 6);
  (17, 6);
  (18, 7);
|];;


(** <h3>Calculer la pente.</h3> *)

let pente ((a1, a2) : point) ((b1, b2) : point) =
  (float_of_int (b2 - a2) ) /. (float_of_int (b1 - a1) );;


(** Choisit la partie inférieure ou supérieure, selon laquelle est la plus proche. *)
let ceil_or_floor myfloat =
  let n1 = ceil myfloat and n2 = floor myfloat in
  (** [n1 <= myfloat <= n2] *)
  if (myfloat -. n2 ) > 0.5 then n1 else n2;;


(** <h3>Une première heuristique pour trouver les ordonnées du segment.</h3> *)

(** Le calcul dépend d'une fonction [mytrunc] qui décide comment arrondir les ordonnées [y_i] en valeurs entières. *)
let calc_segment mytrunc ((a1, a2) : point) ((b1, b2) : point) =
  let n = b1 - a1 in
  assert(n > 0);
  let alpha = pente (a1, a2) (b1,  b2) in
  assert(alpha < 1.);
  assert(alpha > 0.);
  (** Le segment [s] dont on calcule directement les ordonnées [y_i] petit à petit. *)
  let s = Array.init (n+1)
    (fun i -> (
      a1 + i,
      truncate (mytrunc ( (float_of_int a2) +. ( alpha *. (float_of_int i) ) ) )
    ) ) in
  (s:segment)
;;

(** <h4>On a trois exemples, avec [floor], [ceil] et [ceil_or_floor].</h4> *)

(** Cette fonction là est donc l'autre approche proposée en partie [3.] ! *)
let lower = calc_segment floor
and upper = calc_segment ceil
and best = calc_segment ceil_or_floor
;;

(** <h2>L'algorithme de Bresenham, tel qu'il était demandé.</h2> *)

let bresenham ((a1, a2) : point) ((b1, b2) : point) =
  let n = b1 - a1 in
  let e = ref (b1 - a1) in
  let dx = 2 * n in
  let dy = 2 * (b2 - a2) in
  let alpha = pente (a1, a2) (b1,  b2) in
  assert(alpha < 1.);
  assert(alpha > 0.);
  (** Le segment [s] dont on va modifier les abscisses [x_i] et les ordonnées [y_i] petit à petit. *)
  let s = Array.create (n + 1) (a1,a2) in
  (** Début ! Adapté depuis wikipédia, comme le pseudo code de l'énoncé était "faux". *)
  let x1 = ref a1 and x2 = ref b1 in
  let y1 = ref a2 in
  let i = ref 0 in
  while (!x1 <= !x2) do
    s.(!i) <- (!x1, !y1);
    incr x1;
    e := !e - dy;
    if (!e <= 0) then begin
      incr y1;
      e:= !e + dx;
    end;
    incr i;
  done;
  (s:segment)
;;


(** <h3>Un exemple pour chaque fonction.</h3> *)

let d2 = lower a b;;
let d3 = upper a b;;
let d4 = best a b;;
let d5 = bresenham a b;;


(** <h2>Illustration graphique de l'algorithme de Bresenham.</h2> *)
open Graphics;;

(** Alterner les couleurs des carrés quand on en ajoute un, c'est <i>(plus lisible !)</i>. *)

(** Quelques couleurs supplémentaires *)
let marron : color = rgb 84 47 0
and purple : color = rgb 165 0 255
;;

let colors = [| black; red; green; blue; marron; purple |];;
let colors_name = [| "black"; "red"; "green"; "blue"; "marron"; "purple" |];;
let indice_color = ref 0;;
let initcolor () = indice_color := 0;;
let nextcolor () =
  indice_color := (!indice_color + 1) mod (Array.length colors);
  set_color colors.(!indice_color)
;;

(** <h3>Afficher une droite discrète sous forme de petits carrés.</h3> *)

let plot_segment ?(taille = 40) ?(nommethode = "par défaut") (monseg : segment) () =
  let n = Array.length monseg in
  (** Adapter la taille ici, selon le nombre de point. *)
  let origine = 30 in (** Adapter la position de l'origine ici, selon le nombre de point. *)
  open_graph " 600x500";
  set_color black;
  set_window_title (Printf.sprintf ".: Segment de taille %i avec la methode %s :." n nommethode);
  (* resize_window (2*origine + taille*n + 10) (2*origine + taille*n + 10); *)
  initcolor ();
  set_line_width 2;
  let x0, y0 = monseg.(0) in
  (** On recentre en [origine, origine] *)
  let ms = Array.map (fun (x, y) -> (x - x0, y - y0)) monseg in
  (** La droite *)
  draw_segments [| origine, origine, origine + taille*(1 + (fst ms.(n-1) ) ), origine + taille*(snd ms.(n-1) ) |];
  (** On dessine chaque carré, de taille [taille] sur [taille]. *)
  Array.iter (fun (x, y) ->
    nextcolor ();
    draw_rect (origine + x*taille) (origine + y*taille) taille taille;
  ) ms;
;;


(** <h3>Un exemple pour chaque méthode.</h3> *)
(** Cf. test dans le terminal. *)

let test5 (a:point) (b:point) () =
  let d2 = lower a b in
  Printf.printf "\nExemple par la méthode de la sélection inférieure : (appuyer sur [Enter]).";
  plot_segment ~nommethode:"sélection inférieure (lower)" d2 ();
  read_line ();

  let d3 = upper a b in
  Printf.printf "\nExemple par la méthode de la sélection supérieure : (appuyer sur [Enter]).";
  plot_segment ~nommethode:"sélection supérieure (upper)" d3 ();
  read_line ();

  let d4 = best a b in
  Printf.printf "\nExemple par la méthode de la sélection optimale : (appuyer sur [Enter]).";
  plot_segment ~nommethode:"sélection optimale (best)" d4 ();
  read_line ();

  let d5 = bresenham a b in
  Printf.printf "\nExemple par la méthode de la sélection de Bresenham : (appuyer sur [Enter]).";
  plot_segment ~nommethode:"de Bresenham" d5 ();
  read_line ();
;;

(*
Printf.printf "\nExemple en recopiant le segment de l'énoncé : (appuyer sur [Enter]).";;
plot_segment ~nommethode:"énoncé" d1 ();;
read_line ();;
*)
(* test5 a b ();; *)


let test_segment taille =
  Printf.printf "Taille = %i" taille;
  let a : point = (0, 0) and alpha = 2. /. 3. in
  let b : point = (200/taille, int_of_float (alpha *. float_of_int(200/taille)) ) in
  Printf.printf "Avec a = (%i, %i) et b = (%i, %i)" (fst a) (snd a) (fst b) (snd b);
  let s : segment = bresenham a b in
  plot_segment ~nommethode:"de Bresenham" ~taille:taille s ();
  Printf.printf "Avec taille = %i. Appuyer sur [Enter] pour fermer la fenetre ..." taille;
  ignore (read_line ());
  clear_graph ();
;;

let tests () =
  for i = 6 downto 2 do
    for j = 1 downto 0 do
      test_segment (10 * i + 5 * j);
    done;
  done;
  for i = 20 downto 1 do
    test_segment i;
  done;
;;


tests();;

(** <h2>Fin. Des questions ?</h2> *)
(** {%html: <hr> %} *)
(** {%html: <center><small>par Lilian BESSON, avril 2014.</small></center> %} *)

    

bresenhan_cercles.ml

      (** <h1>Représentation des segments en infographie.</h1>

    <h1>Prépa. agreg 2013-2014 : Texte de Modélisation.</h1>

    <b>Date:</b> Mardi 29 Avril 2014.
    @see <http://besson.qc.to/a/m/29-04/public2012-D5.pdf> Sujet.
    @see <http://besson.qc.to/a/m/29-04/> Documentation.
    @author Lilian BESSON
*)


(** <h2>Préliminaires.</h2> *)

(** <h3>Type [point] pour représenter un point [A = (a1, a2)].</h3> *)

type point = int * int;;


(** <h3>Type [courbe] pour représenter une courbe, sous forme de liste de points.</h3> *)

type courbe = point array;;

(** <h3>Type [cercle] pour représenter un cercle, avec son centre et son rayon.</h3> *)
type cercle = { centre: point; rayon: int};;

(** Un exemple *)
let c1 : cercle = { centre = (0, 0); rayon = 7 };;

let c2 : cercle = { centre = (0, 3); rayon = 12 };;


(** <h2>Adaptation de cet algorithme pour des cercles</h2> *)

let get_x ({centre; _}: cercle) = fst centre
and get_y ({centre; _}: cercle) = snd centre
and get_r ({rayon; _}: cercle) = rayon;;

(** Trois types de deplacements *)
let deltax = (1, 0)
and deltay = (0, 1)
and deltaxy = (1, 1);;

(** Qu'on peut appliquer avec cette fonction. *)
let transl (xy: point) delta =
  let x = fst xy and y = snd xy in
  let dx = fst delta and dy = snd delta in
  (x + dx, y + dy);;

(** Et celle la qui modifie les deux references comme il faut. *)
let transl_ref (x: int ref) (y: int ref) delta =
  let dx = fst delta and dy = snd delta in
  x := !x + dx;
  y := !y + dy;
;;


(** Mise au carre d'un entier, puisque [x ** 2] ne marche que pour les flottants... *)
let carre x = x * x;;

(** Une certaine distance entre la courbe cercle et le point xy. *)
let distance_au_cercle (c: cercle) (xy: point) =
  let r = get_r c and x0 = get_x c and y0 = get_y c in
  let x = fst xy and y = snd xy in
  abs( (carre r) - ((carre (x - x0)) + (carre (y - y0))) )
;;


(** Depuis le point xy, trouve lequel des deplacement elementaries dx, dy ou dx+dy permet de rester le plus pret du cercle. *)
let plus_petit_delta (c: cercle) (xy: point) =
  let dx = distance_au_cercle c (transl xy deltax)
  and dy = distance_au_cercle c (transl xy deltay)
  and dxy = distance_au_cercle c (transl xy deltaxy) in
  if dx < min dy dxy then
    deltax
  else begin
    if dy < min dx dxy then
      deltay
    else
      deltaxy
  end
;;


(** On va recuperer la liste des pixels de l'arc (pi, pi/2) en sens anti trigonometrique *)
let pixels_de_cercle (c: cercle): point array =
  let r = get_r c in
  (** On part a gauche, theta = pi *)
  let x0 = (get_x c) - r and y0 = get_y c in
  (** On va en haut, theta = pi/2 *)
  let xfin = get_x c and yfin = (get_y c) + r in
  (** Liste des pixels a afficher, construite progressivement *)
  let pixels = ref [(x0, y0)] in
  let xi = ref x0 and yi = ref y0 in
  (** On est en (xi, yi) *)
  (* while ((!xi < xfin) && (!yi <= yfin) ) || ((!xi <= xfin) && (!yi < yfin) ) *)
  while (!xi, !yi) < (xfin, yfin) do  (** Ordre lexicographique *)
    let delta = plus_petit_delta c (!xi, !yi) in
    transl_ref xi yi delta;
    pixels := (!xi, !yi) :: !pixels;
  done;
  Array.of_list (List.rev !pixels)
;;


(** Un exemple *)
let p1 = pixels_de_cercle c1;;

let p2 = pixels_de_cercle c2;;


(** --------------------------------------- *)

(** <h2>Illustration graphique de l'algorithme de Bresenham.</h2> *)
open Graphics;;

(** Alterner les couleurs des carrés quand on en ajoute un, c'est <i>(plus lisible !)</i>. *)

let colors = [| black; red; green; blue; cyan; magenta |];;
let colors_name = [| "black"; "red"; "green"; "blue"; "cyan"; "magenta" |];;
let indice_color = ref 0;;
let initcolor () = indice_color := 0;;
let nextcolor () =
  indice_color := (!indice_color + 1) mod (Array.length colors);
  set_color colors.(!indice_color)
;;

(** <h3>Afficher une droite discrète sous forme de petits carrés.</h3> *)

let plot_cercle_courbe ?(taille=40) (c: cercle) (monseg: courbe) () =
  let r = get_r c and centrex = get_x c and centrey = get_y c in
  let n = Array.length monseg in
  let taille = taille in (** Adapter la taille ici, selon le nombre de point. *)
  let origine = 30 in (** Adapter la position de l'origine ici, selon le nombre de point. *)
  open_graph " 600x500";
  set_color black;
  set_window_title (Printf.sprintf ".: Quart de cercle de rayon %i et taille %i :." r taille);
  (* resize_window (2*origine + taille*n + 10) (2*origine + taille*n + 10); *)
  initcolor ();
  set_line_width 2;
  let x0, y0 = monseg.(0) in
  (** On recentre en [origine, origine] *)
  let ms = Array.map (fun (x, y) -> (x - x0, y - y0)) monseg in
  (** On dessine le cercle *)
  draw_circle (origine + taille * (centrex - x0)) (origine + taille * (centrey - y0)) (r * taille);
  (** On dessine chaque carré, de taille [taille] sur [taille]. *)
  Array.iter (fun (x, y) ->
    nextcolor ();
    draw_rect (origine + x*taille) (origine + y*taille) taille taille;
  ) ms;
;;


(** Exemples *)

plot_cercle_courbe c1 p1 ();;
ignore (read_line ());;
clear_graph ();;

plot_cercle_courbe ~taille:20 c2 p2 ();;
ignore (read_line ());;
clear_graph ();;


let test_cercle taille =
  let c = { centre = (0, 0); rayon = 200/taille } in
  let p = pixels_de_cercle c in
  plot_cercle_courbe ~taille:taille c p ();
  Printf.printf "Avec taille = %i. Appuyer sur [Enter] pour fermer la fenetre ..." taille;
  ignore (read_line ());
  clear_graph ();
;;

let tests () =
  for i = 7 downto 2 do
    for j = 1 downto 0 do
      test_cercle (10 * i + 5 * j);
    done;
  done;
  for i = 20 downto 1 do
    test_cercle i;
  done;
;;



tests();;

(** <h2>Fin. Des questions ?</h2> *)
(** {%html: <hr> %} *)
(** {%html: <center><small>par Lilian BESSON, avril 2014.</small></center> %} *)

    

cercle-discret__example.gif

cercle-discret__example1.png

cercle-discret__example2.png

cercle-discret__example3.png

cercle-discret__example4.png

droite-discrete__example.gif

Comments (2)

HTTPS

SSH

You can clone a snippet to your computer for local editing. Learn more.