Programmation objet et géométrie/Les lignes droites de canvas

Pour tracer un segment, il suffit de fournir les coordonnées de son extrémité (donc 2 nombres), du moment que c'est après beginPath() et avant stroke(). Les segments sont donc plus faciles à tracer que les courbes de Bézier, et plus rapides à tracer aussi. En plus, en utilisant moveTo() on peut tracer des segments discontinus (ou des graduations). La principale question est où est l'origine du segment?. En fait elle est mémorisée comme la position actuelle du pinceau, définie par le dernier moveTo() ou le dernier lineTo() appliqué. Ceci permet de tracer des polygones ou de représenter graphiquement des fonctions.

Exemples de base

modifier

Segment

modifier

Segment en traits pleins

modifier

L'algorithme est le suivant:

  1. déclarer le début d'un trait de pinceau (tremper le pinceau dans la peinture), avec beginPath();
  2. poser le pinceau au début du trait, avec moveTo();
  3. tirer le trait jusqu'au point d'arrivée, avec lineTo();
  4. lever le pinceau, avec stroke().

Voici un exemple:

<html>
<style type="text/css">
      canvas { border: 4px solid brown; background: #FFFFFF }
</style>
<body>
<canvas id="cadre" width="400" height="200">
<script>
var chevalet=document.getElementById('cadre');
var pinceau=chevalet.getContext('2d');
pinceau.beginPath();
pinceau.moveTo(50,100);
pinceau.lineTo(350,100);
pinceau.stroke();
</script>
</canvas>
<br/>
</body>
</html>

Segment en pointillés

modifier

Avec une boucle

modifier

On peut faire un segment en pointillés avec une boucle, en alternant les traits tracés (avec lineTo()) et les traits non tracés (avec moveTo()):

<html>
<style type="text/css">
      canvas { border: 4px solid brown; background: #FFFFFF }
</style>
<body>
<canvas id="cadre" width="400" height="200">
<script>
var chevalet=document.getElementById('cadre');
var pinceau=chevalet.getContext('2d');
pinceau.beginPath();
pinceau.moveTo(50,100);
for(n=1;n<=30;n+=2){
	pinceau.lineTo(50+n*10,100);
	pinceau.moveTo(60+n*10,100);
}
pinceau.stroke();
</script>
</canvas>
<br/>
</body>
</html>

Une variante permet d'ajouter des graduations (en faisant des pointillés perpendiculaires au segment).

Avec un dégradé

modifier
<html>
<style type="text/css">
      canvas { border: 4px solid brown; background: #FFFFFF }
</style>
<body>
<canvas id="cadre" width="400" height="200">
<script>
var chevalet=document.getElementById('cadre');
var pinceau=chevalet.getContext('2d');
var pointille=pinceau.createLinearGradient(50,100,350,100);
for(n=0;n<=15;n++){
	pointille.addColorStop(n/16,"Black");
	pointille.addColorStop((n+0.499)/16,"Black");
	pointille.addColorStop((n+0.501)/16,"White");
	pointille.addColorStop((n+0.999)/16,"White");
}
pinceau.strokeStyle=pointille;
pinceau.beginPath();
pinceau.moveTo(50,100);
pinceau.lineTo(350,100);
pinceau.stroke();
</script>
</canvas>
<br/>
</body>
</html>

Cette variante, qui nécessite aussi une boucle (pour fabriquer le dégradé), présente l'avantage de s'appliquer aussi à des courbes.

Triangle

modifier

Pour tracer un polygone, il faut faire un lineTo() pour chaque côté (en n'oubliant pas de revenir au point de départ):

<html>
<style type="text/css">
      canvas { border: 4px solid brown; background: #FFFFFF }
</style>
<body>
<canvas id="cadre" width="400" height="200">
<script>
var chevalet=document.getElementById('cadre');
var pinceau=chevalet.getContext('2d');
pinceau.beginPath();
pinceau.moveTo(50,150);
pinceau.lineTo(350,150);
pinceau.lineTo(200,50);
pinceau.lineTo(50,150);//pour refermer le triangle
pinceau.stroke();
</script>
</canvas>
<br/>
</body>
</html>

Une variante consiste à remplir le triangle au lieu de seulement dessiner ses côtés, et dans ce cas le dernier côté n'est pas nécessaire:

<html>
<style type="text/css">
      canvas { border: 4px solid brown; background: #FFFFFF }
</style>
<body>
<canvas id="cadre" width="400" height="200">
<script>
var chevalet=document.getElementById('cadre');
var pinceau=chevalet.getContext('2d');
pinceau.moveTo(50,150);
pinceau.lineTo(350,150);
pinceau.lineTo(200,50);
pinceau.fill();
</script>
</canvas>
<br/>
</body>
</html>

Fonction

modifier

Pour représenter graphiquement une fonction, il suffit de dessiner un polygone ayant beaucoup de côtés assez petits pour donner l'illusion d'une courbe. Par exemple, pour dessiner une parabole on peut faire comme ceci :

<html>
<style type="text/css">
      canvas { border: 4px solid brown; background: #FFFFFF }
</style>
<body>
<canvas id="cadre" width="400" height="400">
<script>
var chevalet=document.getElementById('cadre');
var pinceau=chevalet.getContext('2d');
pinceau.strokeStyle="Red";
pinceau.beginPath();
pinceau.moveTo(0,0);
for(x=0;x<=400;x++){
	pinceau.lineTo(x,400-Math.pow(x-200,2)/100);
}
pinceau.stroke();
</script>
</canvas>
<br/>
</body>
</html>

On peut ajouter des axes gradués avec d'autres boucles:

pinceau.strokeStyle="Blue";
pinceau.beginPath();
pinceau.moveTo(0,400);
pinceau.lineTo(400,400);
for(x=0;x<=400;x+=20){
	pinceau.moveTo(x,400);
	pinceau.lineTo(x,395);
}
pinceau.stroke();

Et quelque chose d'analogue pour l'axe des ordonnées (attention à ne pas oublier qu'il est à l'envers).

Arbre de Stern-Brocot

modifier
 

L'utilisation de boucles JavaScript permet de construire des polygones très complexes, comme par exemple le flocon de Von Koch. Ici on va plutôt dessiner l'arbre de Stern-Brocot. Le dessin d'un arbre se fait par récurrence: Le principe est de dessiner la branche gauche et la branche droite (des segments) puis de rajouter à leur extrémité un (sous-)arbre. Pour calculer les coordonnées des extrémités des segments, on utilise le développement en fraction continue d'une fraction:

Si le développement en fraction continue est [a1,a2,a3,...,an] alors

  1. l'une des branches partant de cette fraction va vers la fraction [a1,a2,a3,...,an+1]; on appellera fils de la fraction cette nouvelle fraction;
  2. l'autre branche va vers la fraction fille, de développement [a1,a2,a3,...,an-1,2].

L'algorithme de tracé de l'arbre peut donc s'écrire

  1. On part d'une fraction, représentée par le point d'abscisse sa valeur et d'ordonnée l'inverse de son dénominateur (par convention)
  2. On tire un segment vers son fils;
  3. On tire un autre segment vers sa fille;
  4. On trace l'arbre du fils;
  5. On trace l'arbre de la fille.

La condition pour finir la récurrence est la taille du dénominateur: S'il est trop grand (en pratique, supérieur ou égal à 400) la fraction est proche de la canopée de l'arbre (l'axe des abscisses) et on s'arrête.

Calculs sur les fractions

modifier

Comme on ne fait pas beaucoup de calculs sur les fractions, il n'est pas absolument nécessaire de créer un objet fraction en JavaScript. On se contentera ici de représenter la fraction   par le tableau [p,q]. De même, la fraction continue (une suite d'entiers naturels) sera représentée par un tableau JavaScript.

Conversion en fraction continue

modifier

L'algorithme de conversion de fraction vers fraction continue (noté ci-dessous frac2cont en anglais: fraction to continued fraction) est assez simple à décrire: Répéter la suite d'opérations

  1. inverser la fraction
  2. soustraire au résultat, sa partie entière (qui se retrouve stockée dans la liste de la fraction continue).

Quelques astuces javascriptiennes ont été utilisées ci-dessous, pour raccourcir le code:

  • Tout d'abord, la condition de sortie de la boucle ne porte pas comme d'habitude sur l'indice n de la boucle mais sur la fraction elle-même (on n'arrête pas lorsque n atteint une valeur prédéfinie, mais lorsque le dénominateur de la fraction est devenu égal à 1).
  • Ensuite, le fait d'utiliser un tableau pour stocker une fraction, permet de l'inverser assez facilement (en plaçant simultanément son dénominateur f[1] comme numérateur, et son numératereur f[0] comme dénominateur).
  • Enfin, la liste des réduites est construite au fur et à mesure: Initialisée comme tableau à une seule entrée avec var cont, chaque tentative d'écriture sur l'indice n+1 qui ne contient encore rien, allonge le tableau:
function frac2cont(f){
	var cont=[Math.floor(f[1]/f[0])];
	for(var n=0;f[1]>1;n++){
		f=[f[1],f[0]];
		f[0]-=cont[n]*f[1];
		cont[n+1]=Math.floor(f[1]/f[0]);
	}
	cont.pop();
	return cont;
}

L'instruction pop vers la fin est dûe à ce que la boucle est parcourue une fois de trop, et donc le dernier élément du tableau contient ∞ à cause d'une division par zéro. JavaScript possède une sorte d'esprit d'initiative, préférant anticiper sur ce que voulait le programmeur, plutôt que tout bloquer avec un message d'erreur (ce qui n'est pas surprenant, on souhaite rarement que l'internaute voie une page bloquée parce que le webmestre a fait n'importe quoi).

Conversion en fraction

modifier

On peut obtenir les réduites d'une fraction continue avec deux suites doublement récurrentes (façon Fibonacci) dont les coefficients sont ceux de la fraction continue. Comme cette fonction JavaScript réalise l'inverse de la précédente, elle est nommée cont2frac (pour l'anglais continued to fraction):

function cont2frac(c){
	//suite des numérateurs et des dénominateurs
	var num=[0,1];
	var den=[1,0];
	for(n in c){
		num=[c[n]*num[0]+num[1],num[0]];
		den=[c[n]*den[0]+den[1],den[0]];
	}
	return [num[0],den[0]];
}

L'usage de ces deux fonctions est typique de pratiquement toutes les maths: On commence (avec frac2cont) par transporter tout le problème dans un espace (celui des fractions continues) où il est plus facile à résoudre; on en profite pour le résoudre, puis on transporte sa solution (par cont2frac) dans l'espace de départ où on peut exploiter sa solution. Ce procédé est si répandu qu'il porte un nom: La conjugaison (exemples connus: Changement de bases en calcul matriciel, transformées de Fourier et de Laplace etc.). Le mot conjugaison semble dù à Galois.

Fils d'une fraction

modifier
function fils(f){
	var cont=frac2cont(f);
	cont[cont.length-1]++;
	return cont2frac(cont);
}


Fille d'une fraction

modifier
function fille(f){
	var cont=frac2cont(f);
	cont[cont.length-1]--;
	cont[cont.length]=2;
	return cont2frac(cont);
}

Les fonctions précédentes sont à mettre dans l'entête (head) du document, celles du dessin de l'arbre pouvant être placées dans le corps (body), entre les deux balises qui ouvrent et ferment le canvas (et même en ajoutant des balises script puisque c'est encore du JavaScript):

Dessin de l'arbre

modifier

Pour simplifier les fonctions JavaScript ci-dessus, on se limite à la partie de l'arbre de Stern-Brocot qui se trouve entre 0 et 1 (ça évite de s'encombrer de parties entières). L'arbre sera donc tracé à partir de la fraction 1/2. Mais la fonction le définissant doit être plus générale, et admettre en entrée une fraction, pour permettre une définition récursive.

Définition récursive

modifier

Pour dessiner l'arbre d'une fraction,

  1. On effectue un moveTo jusqu'à la fraction (abscisse: La fraction; ordonnée: La même, mais en remplaçant son numérateur par 1)
  2. On trace un trait jusqu'à son fils, et on y ajoute l'abre de son fils.
  3. On retourne à la fraction de départ
  4. On trace à trait jusqu'à sa fille;
  5. On ajoute l'arbre de la fille

Ainsi, la définition de l'arbre fait appel à la notion d'arbre, pourtant en cours de définition: Récursivité!. Cette définition récursive est courte et ne nécessite pas de savoir où se trouvent le fils et la fille (l'un d'eux à à gauche, mais on n'a pas besoin de savoir lequel).

function arbre(f){
	if (f[1]<400){
		pinceau.moveTo(400*f[0]/f[1],400/f[1]);
		var f1=fils(f);
		pinceau.lineTo(400*f1[0]/f1[1],400/f1[1]);
		var f2=fille(f);
		pinceau.moveTo(400*f[0]/f[1],400/f[1]);
		pinceau.lineTo(400*f2[0]/f2[1],400/f2[1]);
		arbre(f1);
		arbre(f2);
	}
}

Après ça, il suffit d'appeler la fonction arbre([1,2]) puis un stroke() fait le dessin:

Arbre de Stern-Brocot

modifier
<html>
<head>
<script>
function cont2frac(c){
	//suite des numérateurs et des dénominateurs
	var num=[0,1];
	var den=[1,0];
	for(n in c){
		num=[c[n]*num[0]+num[1],num[0]];
		den=[c[n]*den[0]+den[1],den[0]];
	}
	return [num[0],den[0]];
}
function frac2cont(f){
	var cont=[Math.floor(f[1]/f[0])];
	for(var n=0;f[1]>1;n++){
		f=[f[1],f[0]];
		f[0]-=cont[n]*f[1];
		cont[n+1]=Math.floor(f[1]/f[0]);
	}
	cont.pop();
	return cont;
}
function fils(f){
	var cont=frac2cont(f);
	cont[cont.length-1]++;
	return cont2frac(cont);
}
function fille(f){
	var cont=frac2cont(f);
	cont[cont.length-1]--;
	cont[cont.length]=2;
	return cont2frac(cont);
}
</script>
</head>
<style type="text/css">
      canvas { border: 4px solid brown; background: #FFFFFF }
</style>
<body>
<canvas id="cadre" width="400" height="200">
<script>
var chevalet=document.getElementById('cadre');
var pinceau=chevalet.getContext('2d');
pinceau.strokeStyle="Green";
pinceau.beginPath();
function arbre(f){
	if (f[1]<400){
		pinceau.moveTo(400*f[0]/f[1],400/f[1]);
		var f1=fils(f);
		pinceau.lineTo(400*f1[0]/f1[1],400/f1[1]);
		var f2=fille(f);
		pinceau.moveTo(400*f[0]/f[1],400/f[1]);
		pinceau.lineTo(400*f2[0]/f2[1],400/f2[1]);
		arbre(f1);
		arbre(f2);
	}
}
arbre([1,2]);
pinceau.stroke();
</script>

</canvas>
<br/>
</body>
</html>

L'arbre se calcule presque instantanément mais il est long à afficher. Par contre, en s'arrêtant à l'ordre 40 (au lieu de 400), on a déjà quelque chose qui ressemble à un arbre (sauf qu'on voit moins bien l'alignement de la canopée):

 

Une variante intéressante consiste à diviser l'ordonnée par le dénominateur (400/f[1]/f[1] au lieu de 400/f[1]):

 

En agrandissant (multiplier les abscisses par 800 au lieu de 400), on aperçoit un détail qui aura de l'importance dans le prochain chapitre: