(* exercice avec union-find *)

open Graphics
open Uf (* Programme 72 page 298 *)

let dim = 10 (* matrice dim * dim *)
let int_of_pixel (i, j) = i * dim + j

let calcul_parties_connexes uf t =
  let p = Array.length t in
  for i = 0 to p - 1 do
    for j = 0 to p - 1 do
      if i < p - 1 then
        if t.(i).(j) =  t.(i+1).(j) then
          union uf (int_of_pixel (i, j)) (int_of_pixel ((i+1), j));
      if j < p - 1 then
        if t.(i).(j) =  t.(i).(j+1) then
          union uf (int_of_pixel (i, j)) (int_of_pixel (i, j + 1));
    done
  done

(* affichage graphique *)

let size = 200
let rp = size / dim

let gr i = rp * i

let () = open_graph (Printf.sprintf " %dx%d" size size)

let draw_pixel i j c = set_color c; fill_rect (gr i) (gr j) rp rp

let draw_BW_image t =
  Array.iteri
    (fun i ti ->
       Array.iteri
         (fun j b -> draw_pixel i j (if b then black else white)) ti) t

let inc_color = 83

let new_color =
  let r = ref 10 in
  let g = ref 10 in
  let b = ref 10 in
  fun () ->
    let b' = !b + inc_color in
    let g' = !g + (b' / 255 * inc_color) in
    let r' = !r + (g' / 255 * inc_color) in
    b := b' mod 256;
    g := g' mod 256;
    r := r' mod 256;
    rgb !r !g !b

let draw_COLOR_image uf t =
  let table = Hashtbl.create 200 in
  let p = Array.length t in
  for i = 0 to p - 1 do
    for j = 0 to p - 1 do
      let r = find uf (i * p + j) in
      let c =
        try
          Hashtbl.find table r
        with Not_found ->
          let c = new_color () in Hashtbl.add table r c; c
      in
      draw_pixel i j c
    done
  done

(* test avec une matrice aléatoire *)

let random_bool_matrix p n =
  let random_BW () = Random.int 100 < n in
  Array.init p (fun _ -> Array.init p (fun _ -> random_BW ()))

let t = random_bool_matrix dim 40
let uf = create (dim * dim)
let () = calcul_parties_connexes uf t

let () =
  draw_BW_image t;
  ignore (read_key ());
  draw_COLOR_image uf t;
  ignore (read_key ());

This document was generated using caml2html