le principe de la transformation affine est fort simple : on spécifie
un parallèlogramme dans le plan de l'image de départ, et qui
correspondra à l'image d'arrivée. Le parallèlogramme est
définit à l'intérieur d'un bloc carré de quatre images
(A,B,C,D) par ses coordonnées rationnelles :
(voir figure
8)
On impose par ailleurs
largeur du
parallèlogramme, hauteur du parallèlogramme
.
On a alors deux cas : soit les quatre images sont toutes noires ou toutes blanches et l'image renvoyée est Noir ou Blanc, soit on subdivise le parallélogramme en quatre, et on rappelle la procédure avec chacun des quatre fils avec les quatre variables (parmi les fils des variables précédentes) qui le contiennent, et les valeurs x' et y' mises à jour.
x et y restent entiers car le choix des quatre fils qui contiennent le sous parallèlogramme ne permet que trois possibilités pour x' :
Et x' reste entier puisqu'on a 2d au dénominateur, donc ppcm(2,2d)=2d.
On a bien sûr les mêmes résultats pour y'.
Le nombre de variables créées est donc majoré par (ce qui correspond
au nombre de quadruplets de quatre variables associés à deux
entiers positifs inférieurs à 2d.) Le programme termine donc,
mais est virtuellement en
.
