Exercices

Exercice 1

Exercice 4 du sujet Amérique du Sud J2 2022

Correction Q1.a
🐍 Script Python
from math import sqrt

Q1.b : tester son code

🐍 Script Python
>>> distance_points((3, 5), (7, 4))
4.123105625617661
Correction Q1.b
🐍 Script Python
1
2
def distance_points(a, b):
    return sqrt((b[0]-a[0])**2 + (b[1]-a[1])**2)

Q2 : tester son code

🐍 Script Python
>>> distance((8, 3), (5, 6), (3, 7))
1.3416407864998738
>>> distance((8, 3), (5, 6), (5, 6))
4.242640687119285
Correction Q2.
🐍 Script Python
1
2
3
4
5
def distance(p, a, b):
    if a == b:
        return distance_points(p, a)
    else:
        return distance_point_droite(p, a, b)

Q3 : tester son code

On cherche les coordonnées du point \(M\).

La droite \((AB)\) a une équation du type: \(y=m\times x+od\)

Son coefficient directeur est \(\displaystyle m = \frac{\Delta y}{\Delta x}=\frac{y_B-y_A}{x_B-x_A}\)

L'équation de la droite perpendiculaire à la droite \((AB)\) a un coefficient directeur égal à \(-\frac{1}{m}\).

Son équation est du type: \(y=-\frac{1}{m}x+c\)

Cette droite passant par \(P\) on en déduit: \(c=y_p+\frac{1}{m}x_P\)

Cherchons les coordonnées de \(M\), le point d'intersection des deux droites:

\(m\times x_M+od= -\frac{1}{m}x_M+y_P+\frac{1}{m}x_P\)

En en déduit que \(\displaystyle x_M=\frac{x_P+m(y_P-od)}{1+m^2}\)

Sachant que \(\displaystyle m = \frac{y_B-y_A}{x_B-x_A}\)

On obtient: \(\displaystyle x_M=\frac{x_P(x_B-x_A)+(y_P-od)(y_B-y_A)}{(x_B-x_A)+m(y_B-y_A)}\) et \(y_m=m\times x_M + od\)

Fonction distance_point_droite :

🐍 Script Python
1
2
3
4
5
6
7
8
def distance_point_droite(p, a, b):
    if b[0] == a[0]:
        return abs(p[0]-a[0])
    m = (b[1] - a[1]) / (b[0] - a[0])
    od = a[1] - m*a[0]
    xm = (p[0]*(b[0]-a[0])+(p[1]-od)*(b[1]-a[1])) / (b[0]-a[0] + m*(b[1]-a[1]))
    ym = m*xm + od
    return distance_points(p, (xm, ym))

🐍 Script Python
>>> le_plus_loin([(1, 3), (2, 7), (3, 4), (5, 3)])
(1, 4.0)
Correction Q3.
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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 = ligne[idx]
        d = distance(p, deb, fin)
        if d > dmax:
            dmax = d
            indice_max = idx
    return (indice_max, dmax)

Q4 : tester son code

🐍 Script Python
>>> extrait([(1, 3), (2, 7), (3, 4), (4, 4), (5, 3), (6, 2)], 1, 4)
[(2, 7), (3, 4), (4, 4), (5, 3)]
Correction Q4.
🐍 Script Python
1
2
3
4
5
def extrait(tab, i, j):
    ext = []
    for k in range(i, j+1):
        ext.append(tab[k])
    return ext

ou

🐍 Script Python
1
2
def extrait(tab, i, j):
    return [tab[k] for k in range(i, j+1)]

ou

🐍 Script Python
1
2
def extrait(tab, i, j):
    return tab[i:j+1]

Q5 : tester son code

🐍 Script Python
>>> simplifie([(1, 3), (2, 7), (3, 4), (4, 4), (5, 3), (6, 2)], 3)
[(1, 3), (2, 7), (3, 4), (6, 2)]

image

Correction Q5.
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def simplifie(ligne, seuil):
    n = len(ligne)
    if n <= 2:
        return ligne
    else:
        indice_max, dmax = le_plus_loin(ligne)
        if dmax <= seuil:
            return [ligne[0], ligne[n-1]]
        else:
            return simplifie(extrait(ligne, 0, indice_max), seuil) +  \
                simplifie(extrait(ligne, indice_max, n-1), seuil)

Bonus : mise en pratique de l'algorithme de Douglas-Peucker

Téléchargez d'abord le fichier coord_france.txt puis placez-le dans le même dossier que le code Python ci-dessous :

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from math import sqrt
import matplotlib.pyplot as plt

data = open('coord_france.txt').read().splitlines()
france = []
for couple in data:
    cpl = couple.split(',')
    france.append((int(cpl[0]), int(cpl[1])))

def distance_points(a, b):
    ...

def distance_point_droite(p, a, b):
    if b[0] == a[0]:
        return abs(p[0]-a[0])
    m = (b[1] - a[1]) / (b[0] - a[0])
    od = a[1] - m*a[0]
    xm = (p[0]*(b[0]-a[0])+(p[1]-od)*(b[1]-a[1])) / (b[0]-a[0] + m*(b[1]-a[1]))
    ym = m*xm + od
    return distance_points(p, (xm, ym))  

def distance(p, a, b):
    ...

def le_plus_loin(ligne):
    ...


def extrait(tab, i, j):
    ...

def simplifie(ligne, seuil):
    ...


def trace(ligne, seuil):
    new_ligne = simplifie(ligne, seuil)
    nb_segments = len(set(new_ligne))
    x = [p[0] for p in new_ligne]
    y = [p[1] for p in new_ligne]
    plt.plot(x, y, 'b-', linewidth=0.5)
    plt.text(195014, 2865745, 'seuil : ' + str(seuil))
    plt.text(195014, 2864745, 'nb segments : ' + str(nb_segments))
    plt.axis('equal')
    plt.axis('off')
    plt.show()

trace(france, 0)
Correction
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from math import sqrt
import matplotlib.pyplot as plt

data = open('coord_france.txt').read().splitlines()
france = []
for couple in data:
    cpl = couple.split(',')
    france.append((int(cpl[0]), int(cpl[1])))

def distance_points(a, b):
    return sqrt((b[0]-a[0])**2 + (b[1]-a[1])**2)

def distance_point_droite(p, a, b):
    if b[0] == a[0]:
        return abs(p[0]-a[0])
    m = (b[1] - a[1]) / (b[0] - a[0])
    od = a[1] - m*a[0]
    xm = (p[0]*(b[0]-a[0])+(p[1]-od)*(b[1]-a[1])) / (b[0]-a[0] + m*(b[1]-a[1]))
    ym = m*xm + od
    return distance_points(p, (xm, ym))  

def distance(p, a, b):
    if a == b:
        return distance_points(p, a)
    else:
        return distance_point_droite(p, a, b)

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 = ligne[idx]
        d = distance(p, deb, fin)
        if d > dmax:
            dmax = d
            indice_max = idx
    return (indice_max, dmax)


def extrait(tab, i, j):
    ext = []
    for k in range(i, j+1):
        ext.append(tab[k])
    return ext

def simplifie(ligne, seuil):
    n = len(ligne)
    if n <= 2:
        return ligne
    else:
        indice_max, dmax = le_plus_loin(ligne)
        if dmax <= seuil:
            return [ligne[0], ligne[n-1]]
        else:
            return simplifie(extrait(ligne, 0, indice_max), seuil) + simplifie(extrait(ligne, indice_max, n-1), seuil)


def trace(ligne, seuil):
    new_ligne = simplifie(ligne, seuil)
    nb_segments = len(set(new_ligne))
    x = [p[0] for p in new_ligne]
    y = [p[1] for p in new_ligne]
    plt.plot(x, y, 'b-', linewidth=0.5)
    plt.text(195014, 2865745, 'seuil : ' + str(seuil))
    plt.text(195014, 2864745, 'nb segments : ' + str(nb_segments))
    plt.axis('equal')
    plt.axis('off')
    plt.show()

trace(france, 0)

Le rendu avec un seuil égal à 0 est celui-ci :

image

Vous pouvez faire varier le seuil entre 0 et 5000 et observer les modifications.