Figures récursives

Avec des cercles

La figure suivante peut être décrite de façon récursive :

La figure est formée d’un cercle initial

Deux copies de ce cercle, ayant subies une réduction d’un facteur 2, sont ajoutées. Ces deux petits cercles étant tangents extérieurement au cercle initial et tels que les lignes des centres sont parallèles aux axes du repère.

Chacun de ces deux petits cercles devient à son tour “cercle initial” pour poursuivre la figure…

On peut traduire avec Python ce descriptif récursif de la façon suivante :

import pylab
F = pylab.gca() # F peut être vue comme un objet ’figure’

def cercle(x, y, r):
   """ cercle de centre (x,y) et de rayon r """
   # création du cercle:
   cir = pylab.Circle([x, y], radius = r, fill = False)
   # ajout du cercle à la figure :
   F.add_patch(cir)

def CerclesRec(x, y, r):
   """ construction récursive de la figure """
   cercle(x, y, r)
   if r > 1:
      CerclesRec(x+3*r/2, y, r/2)
      CerclesRec(x, y-3*r/2, r/2)

# appel de la fonction CerclesRec
CerclesRec(0, 0, 8)

# pour placer toute la figure dans un repère orthonormé :
pylab.axis('scaled')
# affichage de la figure :
pylab.show()

En plus des paramètres « abscisse du centre », « ordonnée du centre » et « rayon du cercle », on pourra utiliser un paramètre supplémentaire « position du voisin » pour définir la fonction récursive. »position du voisin » sera l’une des chaînes de caractères : « haut », « bas », « droite » ou « gauche ».

import pylab
F = pylab.gca() # F peut être vue comme un objet ’figure’

def cercle(x, y, r):
   """ cercle de centre (x,y) et de rayon r """
   # création du cercle:
   cir = pylab.Circle([x, y], radius = r, fill = False)
   # ajout du cercle à la figure :
   F.add_patch(cir)

def CerclesRec(x, y, r, pos=""):
   """ construction récursive de la figure """
   cercle(x, y, r)
   if r > 1:
      if pos != "o":
         CerclesRec(x+3*r/2, y, r/2, pos = "e")
      if pos != "n":
         CerclesRec(x, y-3*r/2, r/2, pos = "s")
      if pos != "e":
         CerclesRec(x-3*r/2, y, r/2), pos = "o")
      if pos != "s":
         CerclesRec(x, y+3*r/2, r/2), pos = "n")

# appel de la fonction CerclesRec
CerclesRec(0, 0, 8)

# pour placer toute la figure dans un repère orthonormé :
pylab.axis('scaled')
# affichage de la figure :
pylab.show()

Avec des rectangles

pylab.Rectangle((x,y), a, b, fill=False)  permet de définir un rectangle dont les côtés, de longueurs a et b, sont parallèles aux axes et dont le sommet “sud-ouest” a pour coordonnées (x,y).

Avec des triangles

L’instruction pylab.Polygon([(xa,ya), (xb,yb), (xc,yc)], fill=False) permet de définir un triangle dont les sommets ont pour coordonnées (xa,ya), (xb,yb), (xc,yc).

Flocon de Koch

Le flocon de Koch est également une figure récursive :

Courbe de Koch

Pour commencer nous allons construire, toujours de manière récursive, la courbe de Koch :

Soit un segment initial \(\left[P_1P_5\right]\)

À chaque itération, le segment est coupé en 3 parties de même longueur, ajoutant 2 points intermédiaires \(P_2\) et \(P_4\) sur le segment initial

Un 5^ème point \(P_3\) est formé de sorte d’obtenir un triangle équilatéral avec les 2 points intermédiaires.

On obtient ainsi 4 segments, à partir desquels on peut construire de nouvelles courbes de Koch …

Nous implémenterons les points en Python par des tuples de 2 nombres.

On pourra vérifier visuellement le résultat grâce au programme ci-dessous :

import matplotlib.pyplot as plt

p1 = (1, 2)
p5 = (3, 3)

p2 = ...
p4 = ...

plt.plot(*p1, '.b')
plt.plot(*p2, '.r')
plt.plot(*p4, '.r')
plt.plot(*p5, '.b')
ax = plt.gca()
ax.set_aspect('equal', adjustable='box')
plt.show()

Pour déterminer le dernier point \(P_3\) de la courbe, on procède par rotation d’un angle de 60° du segment \(\left[P_2P_4\right]\)

Pour cela, on utilise une matrice de rotation qui permet d’obtenir le vecteur \(\overrightarrow{P_2P_3}\) par rotation de 60° du vecteur \(\overrightarrow{P_2P_4}\):

\(\overrightarrow{OP_3}=\overrightarrow{OP_2}+\left[ {\begin{array}{cc}
\cos\theta & \sin\theta \\
-\sin\theta & \cos\theta \\
\end{array} } \right]\cdot \overrightarrow{P_2P_4}\)

M = np.array([[0.5, -np.sqrt(3)/2],[np.sqrt(3)/2, 0.5]])

def rotation60(p1, p2):
    """ Retourne le point p2 tel que 
        le segment p1p3 soit obtenu par rotation de 60°
        du segment p1p2
    """
    OP1 = np.array(p1)
    OP2 = np.array(p2)
    OP3 = OP1 + np.dot(M, OP2-OP1)

    return OP3.tolist()

On pourra vérifier visuellement le résultat grâce au programme ci-dessous :

x, y = zip(*koch(4))
plt.plot(x, y)
plt.xlim(-0.1, 1.1)
plt.ylim(-0.1, 0.4)
plt.xticks([])
plt.yticks([])
ax = plt.gca()
ax.set_aspect('equal', adjustable='box')
plt.axis("off")
plt.show()

Extension en Flocon