V2 : les trapèzes

Algorithme de répartition des diminutions pour la création d'un trapèze

On considère un trapèze de bases n et m, de hauteur k ; on considère sans perte de généralité que n>m. Le nombre de diminutions à réaliser en tout à gauche et à droite sont respectivement de d_g et d_d (on a donc n = d_g + m + d_d).

Sans perte de généralités, intéressons-nous au côté gauche (et notons simplement d_g = d).

• si d=<k, alors on répartit un premier paquet de diminutions tous les k/d (arrondi au supérieur) = T rangs. On veut ensuite répartir les diminutions restantes sur les rangs où il n'y en a pas encore (au nombre de k-T) : pour cela, on utilise un algorithme similaire, mais appliqué à k-T rangs. On réitère l'algorithme jusqu'à ce que toutes les diminutions aient été placées.

• si d>k, on va chercher à se ramener à la situation précédente, en répartissant k/d (je ne suis pas sûre de l'arrondi) diminutions sur chaque rang, on peut appliquer l'algorithme précédent aux diminutions restantes.

Un autre algorithme m'a été suggéré : http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_segment_de_Bresenham Il est peut-être effectivement plus simple à mettre en oeuvre...

V3 : tresses