demi-plan oblique

L'introduction de la recursivité permet de représenter parfaitement des parties de obtenue par intersection de avec un demi-plan défini par une équation affine à coefficients rationnels. En effet, soit où est un tel demi-plan (, , entiers relatifs), alors il y a trois cas possibles. Les deux premiers cas sont , alors et , alors .

Dans le troisième cas, est en partie contenu dans , or, si on pose , alors , où les sont définis par des équations de la forme . Or, si les quatre sommets de sont contenus dans (respectivement en dehors de ), alors est tout entier contenu dans (respectivement en dehors). Donc, si , , , et , alors (respectivement, si , , , et , alors , modulo un ensemble de mesure nul).

Donc si et seulement si . Or et de même , donc

Finalement, si on montre que les sont entiers, on aura montré que l'arbre qui représente a au plus nuds, ou encore qu'on peut effectivement représenter avec un arbre quaternaire.

Or, si sont les coordonnées dans et celles dans l'un des quatre ``sous-'', on a où ou .

Donc l'équation de P devient

c'est à dire

Donc , qui est bien un entier relatif.

La routine CAML qui construit un demi-plan oblique à partir des coefficients a, b et c est la suivante :

(* partie de la forme a*x+b*y+c>=0 avec a, b et c entiers relatifs *)

let oblique a b c =

let deja_vues = ref []
and mn = min (min a b) (min 0 (a+b))
and mx = max (max a b) (max 0 (a+b))
in

let rec oblique_aux = function
  c -> if c+mn>=0 then ref (Color Noir)
       else if c+mx<=0 then ref (Color Blanc)
            else try assq c !deja_vues with
                 Not_found -> let h = ref Fantome
                              in deja_vues := (c, h)::(!deja_vues);
                                 h := Node [ oblique_aux (2*c);
                                             oblique_aux (a+2*c);
                                             oblique_aux (a+b+2*c);
                                             oblique_aux (b+2*c) ];
                                 h

in !(oblique_aux c)
;;

Ainsi, sachant représenter l'union et l'intersection de deux images, ainsi que les demi-plans rationnels, on est en mesure de calculer l'arbre associé à n'importe quel polygone dont les cotés sont définis par des coordonnées rationnelles..