Sujet 7 (H)

Étant donné un polygone dans le plan, vous devez dire s'il est étoilé ou non. Un polygone est dit étoilé s'il existe un point du plan P tel que pour tout autre point du polygone Q, le segment [P;Q] est dans le polygone. En particulier, un polygone convexe est toujours étoilé (tout point P du polygone convient).

Par exemple, un triangle est toujours étoilé puisqu'il est convexe. Tout quadrilatère est également étoilé, même s'il n'est pas forcément convexe. La figure suivante contient un polygone qui n'est pas étoilé.

Si vous avez besoin à un moment dans votre algorithme de vérifier si un point est à l'intérieur d'un polygone, réfléchissez au nombre d'intersections avec des arêtes du polygone qu'aurait une demi-droite partant du point considéré.

L'entrée du programme contient une liste de coordonnées sous la forme suivante:

xa ya xb yb xc yc

Cette liste de coordonnées correspond aux points A, B, C... rencontrés en décrivant le périmètre du polygone considéré. Attention, le premier point n'est pas répété à la fin par soucis d'économie.

Pour plus de simplicité, le polygone est considéré comme étant simple, c'est à dire que l'intersection de deux de ses arêtes est toujours vide (elles ne se croisent donc pas). Attention aux problèmes de précision, nous vous conseillons d'être prudent avec les éventuels arrondis. Les tests pour cet exercice ne sont pas là pour vous pièger sur ces aspects donc profitez-en pour assurer un peu les calculs (en particulier en cas d'égalité : on dira par exemple que a = b si b - 0.001 < a < b + 0.001).

Enfin, toujours pour plus de simplicité, les arêtes orientées A->B, B->C etc sont telles que l'intérieur du polygone est toujours du côté des angles indirects par rapport à cette arête (0 0 1 0 1 1 0 1 n'est pas une description valide de polygone).

La sortie de votre programme devra contenir soit "true" soit "false" selon que le polygone décrit par l'entrée est étoilé ou non. La réponse sera suivie d'un retour à la ligne.

Squelettes de codes :

(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les 
mettre dans des variables, et afficher votre resultat final en sortie. *)

(* fonction pour separer les elements en entree 
Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme !*)
    let split_spaces chaine =
      let res = ref [] in
      let temp = ref "" in
  for i = 0 to String.length chaine - 1 do
    if chaine.[i]=' '
    then 
      begin
        res := !res @ [!temp];
        temp := "";
      end
    else
      temp := !temp ^ (String.sub chaine i 1);
  done;
  res := !res @ [!temp];
  !res;;
  
let coordonnees = Array.of_list (List.map float_of_string (split_spaces (input_line stdin)));;

(* Les coordonnees sont maintenant connues ! *)

(* fonction pour afficher votre solution *)
let affiche_solution i =
  if i then print_string "true" else print_string "false";
  print_newline();;

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Debut de votre programme *)


(* Fin de votre programme *)