Exercice 4 · Bac Numérique et Sciences Informatiques Amérique du Sud 2022 (jour 2)

Exercice 4 (4 points)

Cet exercice porte sur la programmation en Python, la récursivité et la méthode "diviser pour régner".

Une ligne polygonale est constituée d'une liste ordonnée de points, appelés sommets, joints par des segments. L'algorithme de Douglas-Peuker permet de simplifier une ligne polygonale en supprimant certains de ses sommets. L'effet de l'algorithme appliqué aux lignes polygonales du contour de la France métropolitaine est illustré ci-dessous.

On implémentera cet algorithme dans la dernière question de l'exercice. Pour cela nous allons d'abord implémenter des fonctions auxiliaires.

On suppose dans la suite que les sommets sont des points du plan dont les coordonnées $(x,y)$ dans un repère orthonormé fixé sont représentées par des tuples de longueur 2.

1.

La distance qui sépare deux points $A$ et $B$ de coordonnées $(x_A, y_A)$ et $(x_B, y_B)$ est donnée par la formule $\sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$.

On rappelle que la fonction sqrt du module math de Python renvoie la racine carrée d'un nombre positif ou nul.

a.

b.

def distance_points(a, b):

2.

On dispose d'une fonction distance_point_droite(p, a, b) qui prend en argument les tuples représentant les coordonnées respectives des points $P$, $A$ et $B$, et qui renvoie la distance du point $P$ à la droite $(AB)$. L'exécution de cette fonction produit une erreur dans le cas où les points $A$ et $B$ sont égaux.

À l'aide des fonctions distance_points et distance_point_droite, écrire une fonction distance(p, a, b) qui renvoie la distance entre le point $P$ et la droite $(AB)$ si les points $A$ et $B$ sont distincts et la distance $AP$ sinon.

def distance(p, a, b):

Dans la suite, on dira que la fonction distance calcule la distance entre le point $P$ et les points $A$ et $B$, éventuellement confondus.

3.

On a besoin d'une fonction le_plus_loin(ligne) qui prend en argument une liste de tuples représentant les coordonnées des points d'une ligne polygonale.

Cette fonction doit renvoyer un tuple composé de:

l'indice du point de coordonnées p de la ligne polygonale d'extrémités deb et fin, pour lequel la distance distance(p, deb, fin) est la plus grande;

la valeur correspondante de cette distance.

On fournit le code incomplet suivant:

Recopier et compléter le code de cette fonction.

def le_plus_loin(ligne):

n = len(ligne)

deb = ligne[0]

fin = ligne[n-1]

dmax = 0

indice_max = 0

for idx in range(1, n-1):

p =...

d = distance(p, deb, fin)

if...:

...

...

return...

4.

Écrire une fonction extrait(tab, i, j) qui renvoie la copie du tableau tab des cases d'indice i inclus à j inclus pour $0 \le i \le j < \text{len}(tab)$.

L'appel extrait([7, 4, 9, 12], 2, 3) renverra ainsi [9, 12].

def extrait(tab, i, j):

L'algorithme de Douglas-Peuker repose sur une stratégie de type « diviser pour régner ».

Pour éliminer des sommets « proches de l'alignement », un seuil est fixé.

Étant donnée une ligne polygonale, le principe de l'algorithme est le suivant:

si la ligne ne contient qu'un ou deux sommets, l'algorithme se termine;

sinon, on considère la droite formée par les extrémités de la ligne (son premier et dernier sommet), et on sélectionne le point le plus éloigné de cette droite (dans le cas où les extrémités sont confondues, on sélectionne le point le plus éloigné de celles-ci):

si la distance entre le point sélectionné et la droite (ou les extrémités lorsqu'elles sont confondues) est inférieure au seuil fixé, on ne conserve que les extrémités de la ligne polygonale;

sinon, on applique l'algorithme de manière récursive aux deux parties de la ligne polygonale formées de la séquence formée du premier sommet jusqu'au sommet sélectionné d'une part et de la séquence formée du sommet sélectionné jusqu'au dernier sommet d'autre part. L'algorithme renvoie alors la concaténation des séquences simplifiées ainsi obtenues.

L'algorithme appelé sur la ligne polygonale [A,B,C,D,E,F,G] ci-dessus, va récursivement être appelé sur les lignes polygonales [A,B,C] et [C,D,E,F,G].

La ligne polygonale que l'on obtiendra à la fin de l'algorithme sera [A,C,E,G].

5.

L'algorithme de Douglas-Peuker est implémenté par la fonction simplifie ci-dessous, qui prend en argument la ligne polygonale et le seuil choisi.

Recopier et compléter le code de cette fonction.

def simplifie(ligne, seuil):

n = len(ligne)

if n <= 2:

return...

else:

indice_max, dmax = le_plus_loin(ligne)

if dmax <= seuil:

return...

else:

# bloc à écrire